Re: BASIC to RPL translation. Message #27 Posted by Egan Ford on 2 Feb 2008, 4:23 a.m., in response to message #26 by Marcus von Cube, Germany
I get the same answer in 187 seconds (50g, 75 Mhz (normal speed), HPGCC2). I expect to cut this down to 90 seconds or less when running at 192 MHz (HPGCC3). The same program on a PC took 3 seconds. IOW, this was an easy problem.
The rapid factoring of 69^{96}  1 used a combination of Trial Division, BrentPollard, William's (p+1), Pollard's (p1), Lenstra's Elliptic Curve, and finally Multiple Polynomial Quadratic Sieve to factor the last composite (9766855675859070369088561). MPQS is a memory hog if the number exceeds 20 digits long. It would be nice if HPGCC2/3 could use the SD card as swap space.
All the above methods are part of MIRACL. I used HPGCC2/3 to port MIRACL to the 50g.
Factoring Valentin's constant (7171...) has been troublesome. On the 50g I can factor out primes 101 * 109 * 21525175387 * 13731482973783137 * 218301576858349, but run out of memory when trying to factor the composite factor: 100961145201957073451533549109227190924435969452249880258549. I need time to tune the other methods.
As for the other problems (BTW, they are very unpleasant), I can factor out the following:
71^{71}  50^{49} = 3 * 7 * 13 * 587 * 787 * 1061 * 3238349 * 516126363001 * (103 digits long)
71^{71} + 2008^{ }= 3 * 3 * 7 * 11 * 73 * 97 * 1213931 * 68637133 * 131118479 * (103 digits long)
71^{71} + 50^{49} = 1038268631 * 1607804243009567 * (108 digits long)
I factored the above using a 50g/HPGCC2 simulator (HPAPINE), and skipped MPQS because I knew it would fail on the 50g. The reported prime factors are found quickly, then there is a lot of computing with no results other than a large composite factor.
IANS, I may be able to improve on this as I find the time. The MIRACL FACTOR can factor very quickly any number that the 50g FACTOR can factor and many more numbers that the 50g cannot factor (e.g. 1152921515344265237).
Lastly, if any are interested in C programming on the 50g then read my tutorial at http://sense.net/~egan/hpgcc.
