Math routine problems

[Doug Telford]

I understand the need to have common routines for all versions of Shen, but some of the routines in StLib are unsuitable for some computations:

(time (gcd 1307674368000 1307674368001))

I killed it after several hours.

The mod function is more than 100 times slower than the Shen-scheme 32 native version for 13 digit numbers.

[Mark Tarver]

At this point I point out the truth that's it's all open source v 1.0 and people are fine in 

changing the code to be faster as long as it still continues to work.

Mark

--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+un...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/qilang/dff9e9b8-1a5b-48e2-95ad-bab0a64eb890n%40googlegroups.com.

[Doug Telford]

The math routines could be greatly improved if we had integer division for all valid integers.

[Mark Tarver]

That's not the issue in the example you've provided.  The problem is that the algorithm

works in linear time in relation to the size of the least number which is very large in this case.

A great improvement can be gained by using Euclid's algorithm which is why probably

the other versions are faster.  

Mark

To view this discussion on the web, visit https://groups.google.com/d/msgid/qilang/73b7e70f-3ec0-4273-a65a-130c8db5f19an%40googlegroups.com.

[Mark Tarver]

For example using Euclid

(time (gcd 1307674368000 1307674368001))

run time: 0.0 secs
1 : number

Mark

To view this discussion on the web, visit https://groups.google.com/d/msgid/qilang/73b7e70f-3ec0-4273-a65a-130c8db5f19an%40googlegroups.com.

[Mark Tarver]

I've updated the library to use Euclid's method.  SP has been updated over the cloud.

Mark

[Doug Telford]

Many computation areas, such as cryptography (RSA algorithm) and Integer factoring (quadratic sieve and Pollard Rho) require computations with 100+ digits.  

If N = (- (expt 2 257) 1) then in shen-scheme if I use the scheme versions of mod and gcd with the Pollard Rho algorithm I can get a factor of the 78 digit number N in about 20 seconds.

If  T1= 17488867867874428608668905378271914447104113100929719303752462256201294163654284611398059217109636255162842814421394166957819840293429944269396711335078378

and 

T2 = 51781680040075356565451107688460143008819366290089498911128844840275340195235

then during the above computation of  Pollard Rho, the following computations are performed:

(mod T1 N)

(gcd T2 N)

Computations similar to the first one above are performed about 14 million times and the second one about 70000 times.

The first computation will not be computed once in a reasonable time (hours?)  with StLib.

Let me know if second one will complete once  in a reasonable time using your revised gcd method.

So it appears to me that integer divide is necessary to efficiently compute mod or rem or quotient, and one of these is needed for an efficient gcd.

Use of floating point is not useful with big numbers since they are only accurate to about 18 digits.

[Mark Tarver]

There's nothing wrong with having fast integer division in stlib.  My point was more
limited which was that the culprit in the original example you showed was not the lack
of fast integer division, but the magnitude of the arguments fed to the main loop.  
Euclid's method works by changing these magnitudes and involved adding 4 more lines
of code which totally changed runtime performance.

Euclid is not the final word in this matter because there are faster versions yet
involving yet more code.  The Euclidean algorithm using mod is faster yet.  Beyond
that faster methods involve processes which involve junking the main loop and
adopting more complex and less intuitive procedures.  But they don't really hinge on fast

integer division.

I never tried 100 digit numbers which lie outside the maxint limit of many platforms.
I tried gcd with digits of 2^32 (I think 2^31 is maxint of Java) and got answers.

(2-) (time (gcd (expt 2 32) (- (expt 2 16) 5)))

run time: 0.3429999351501465 secs
1

As said in my original reply, anybody is free to change to change the code.

Mark