Using BigNum for Programming exercise from HP Forum

Discuss your code, get questions answered

Using BigNum for Programming exercise from HP Forum

Postby d_motto » Sat Mar 22, 2014 8:44 am

I refer to this thread:

http://www.hpmuseum.org/forum/thread-916.html

Calculate the sum of 1-1/2+1/3-1/4...+1/9999-1/10000.

In trying to show up the HP Prime, I wrote my first attempt like this:

Code: Select all
function () {
var t = 1;
for (var j = 2; j <= 10000; j++) {
   if (calculator.functions.isEven(j))
      t = t - 1/j;
   else {
      t = t + 1/j;
          }
    }
    return (t);
}


This comes up with 0.693097183059958

My second try is

Code: Select all
function () {
var t = 1;
for (var j = 10000; j >= 2; j--) {
   if (calculator.functions.isEven(j))
      t -= 1/j;
   else {
      t += 1/j;
          }
    }
    return (t);
}


(This follows the instruction to work from right to left). It comes up with 0.693097183059949; the last two digits are 49 instead of 58.

Now, I wanted to get more precision, so I thought I could use BigNum for that, but I get an error with this code (basing on my first attempt:

Code: Select all
function () {
var t = BigInt.ONE;
var n - t;
var a;
for (var j = 2; j <= 10000; j++) {
   a = BigNum("/"](n,j);
   if (calculator.functions.isEven(j))
      t = BigNum["-"](t,a);
   else {
      t = BigNum["+"](t,a);
          }
    }
    return (t);
}


I get this message:
'undefined' is not an object


So, what I am doing wrong? I have looked at all of the code I can find about BigNum, and considered using other options like toBigF (and RPL+) for this exercise.

David Motto
d_motto
 
Posts: 35
Joined: Tue Apr 17, 2012 9:19 am

Re: Using BigNum for Programming exercise from HP Forum

Postby d_motto » Sat Mar 22, 2014 12:44 pm

Of course, this is how I would do it in RPL+

Code: Select all
<< 1 10000 2 FOR r r @dup IF isEven THEN inv - ELSE inv + END -1 STEP >>


Which gives 0.693097183059949 as well (same as my second attempt); this takes a bit of time.

If I try this code:

Code: Select all
<< 1 toBigF 10000 2 FOR r r @dup IF isEven THEN toBigF inv - ELSE toBigF inv + END -1 STEP >>


it takes so long that I don't want to wait around for it (even if I go from 10 to 2 it takes a bit of time, and of course the number is not close to the actual result I am looking for).

Elapsed time for the second JavaScript program (the countdown method) is about 0.21 seconds, and for the non-BigFloat RPL+ program above is about 2.5 seconds.

David Motto
d_motto
 
Posts: 35
Joined: Tue Apr 17, 2012 9:19 am

Re: Using BigNum for Programming exercise from HP Forum

Postby oliver » Mon Mar 31, 2014 1:22 am

Hi David,

Ok, so sadly BigFloat's "inv" function is expensive and slow.
Creating 1000 or 10000 BigFloats is fast
<< 1..1000 toBigF >>
but if you run "inv" on that you see how slow it is, even without any other code doing additional processing.

Your BigNum code had a couple of syntax problem. Not sure which are a result of transcribing the code for your post.
In summary: BigInt.ONE should be BigInteger.ONE or "cons.big1", "var n - t" was almost certainly "var n = t" and "BigNum("/"]" really "BigNum["/"]". The real showstopper however is the divide: BigNum is "big integer" only and divide will produce a integer result. So... this is pretty useless.

Your single-precision JS code is probably much sped-up, if you add an /*as is*/ comment:
Code: Select all
function () { /*as is*/

This (undocumented) feature disables the conveniences of giving you automagic access to variables and function names but gives you full speed. Might be up to 10x faster.
Without it, you can write "isEven" instead of "calculator.functions.isEven", by the way. (Since v1.4 you can write ME instead of calculator.functions. So ME.isEven or ME.vector.dot (as an example of accessing a different function collection) works.)

Switching from RPL+ to JS for BigFloat code will do very little, because 95% of the expense will be in BigFloat functions, which execute at the same speed.

Eliminating the IF THEN ELSE might speed up the RPL+ code quite a bit. The thread your referencing has ideas for that.
I give coming up with a fast-running double-precision version a try in the next few days, but for multi-precision you're unfortunately stuck with a slow "inv" function on BigF.

Cheers.
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Re: Using BigNum for Programming exercise from HP Forum

Postby oliver » Mon Mar 31, 2014 1:40 am

How fast does
Code: Select all
≪ 1..10000 inv unzip total swap total swap - neg ≫

run on your device?

Simply inserting one toBigF makes it arbitrary-resolution capable
Code: Select all
≪ 1..10000 toBigF inv unzip total swap total swap - neg ≫

but it's dog slow.

You can vary the precision with the setBigFPrecision command. The default is 32 digits (use bigFPrecision to retrieve the current precision value). Lesser number of digits -> greater speed. But it's never gonna be anywhere near as fast as the built-in double-precision type (64-bit -> ~15 digits).
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Re: Using BigNum for Programming exercise from HP Forum

Postby oliver » Tue Apr 01, 2014 9:06 pm

Tried a few versions:

- the vector-based RPL+ code above runs in 0.024s on an iPhone 5s.

- the following RPL+ runs in 0.08s:
Code: Select all
≪ 0 =sum 1 1e4 FOR n 1/(n*(n+1)) =+sum 2 STEP sum ≫

(Not surprising this is slower. RPL FOR-loops aren't speed devils.)

- the following JS code runs in ~0.003s:
Code: Select all
function() { /*as is*/
    var sum = 0;
    for (var n=1; n<1e4; n += 2)
        sum += 1/n - 1/(n+1);
    return sum;
}   

For such short run-times, the reported run-time is often inaccurate.
If the end value for n is upped to 1e6 (a million), the run-time is 0.074s. That is, the time for 1e4 would more accurately be 0.00074s.

Finally, this
Code: Select all
function() { /*as is*/
    var sum = 0;
    for (var n=1; n<1e4; n += 2)
        sum += 1/(n*(n+1));
    return sum;
}   

runs in 0.00062s (derived from the time it takes for 1e6: 0.062s).
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Re: Using BigNum for Programming exercise from HP Forum

Postby oliver » Wed Apr 02, 2014 10:03 am

Just posted a note on how to bench programs/functions: http://forums.naivedesign.com/viewtopic.php?f=17&t=1020
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm

Re: Using BigNum for Programming exercise from HP Forum

Postby d_motto » Sat Apr 05, 2014 11:45 am

Oliver, thanks for the replies.

On my Ipod Touch 4, the RPL+ code takes about .1 seconds (I changed it to this, to follow the instructions):

Code: Select all
≪ 10000..1 inv unzip total swap total swap - neg ≫


The answer comes up as 0.693097183059948, and when I subtract that from the result, I get these extra digits:
3.330669078754696e-16.

The result given in the original challenge was to 30 places, which is why I wanted the toBigF answer.

If I change the starting number to 1e5, I get a closer approximation of ln(2) in a little less than a second; 16 causes it to take about 10 seconds, and 1e7 made it reset (too big of a vector?).

David
d_motto
 
Posts: 35
Joined: Tue Apr 17, 2012 9:19 am

Re: Using BigNum for Programming exercise from HP Forum

Postby oliver » Sat Apr 05, 2014 6:13 pm

Thanks for reporting the run-time on your iPod touch.

Yes, your crash with 1e7 should be explained by the fact that a vector of 10 mio doubles takes 80 MB. The unzip instruction will temporarily double that, and 160 MB is a bit much on that device...

I'd recommend you go for the second implementation in RPL+, which uses a FOR-loop and thereby almost no memory. (Or, better yet, the JS versions.)

A limit of 1e7 actually works on the iPhone 5s, which has quite a bit more memory and horse power (plus, ND1 runs in 64-bit there).
It takes 11s and produces a result that's (only) accurate to 7 places when compared to ln(2).
A limit of 1e6 gives 5 places in 1.1s.

With the original limit of 1e4 only giving 3 places of accuracy, it really shouldn't matter what digits 15 and 16 are doing. If you're seeing a discrepancy between a typed-in 15-digit result and the computed result, that wouldn't be surprising: Discrepancies smaller ~1e-15 are within the limits of IEEE 754 floating-point representation.
oliver
Site Admin
 
Posts: 433
Joined: Sat May 01, 2010 2:11 pm


Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest

cron