Re: TI-M: Re: TI-Math Digest V1 #22


[Prev][Next][Index][Thread]

Re: TI-M: Re: TI-Math Digest V1 #22




In a message dated 6/11/00 4:30:44 PM Mountain Daylight Time, 
noveck@pluto.njcc.com writes:

>  Not really worth it?  Say 2311 is a factor - you'd have to trial divide 485
>  probable primes by 2, 3, 5, 7, and 11.  That's gotta take a good bit of
>  time?

Well, you wouldn't really need to divide the probable primes by anything, 
just trial-dividing the number by the probable primes.  485 trial-divisions 
takes maybe 2 or 3 seconds on the Z80 with assembly integer functions (less 
with faster routines); much faster with an m68k, I'm sure.

>  don't forget 11.  I think that checking whether or not it's prime first is
>  worth it, since it's just a simple binary search - what is that, 12
>  iterations max?  When 70% of your probables ar primes, it's that much more
>  likely to save time. . .

Well what I'm saying is instead of first taking the modulus 2310 and then 
searching for the value in the congruency list, why not just trial-divide by 
2, 3, 5, 7, and 11?  You'd have to do that anyway at some point if you were 
to use wheeler factorization at all.  If the value of the number modulus 2310 
isn't found in the congruency list, that just tells you that the number is 
divisible by 2, 3, 5, 7, and/or 11...

>  > Give TI *some* credit, then ;)
>  
>  Let's time it on a HP49G first =)

I have some speed comparisons on that handy, as a matter of fact ;)  Here's a 
few examples:

38 200 901 201 = 89 * 11 551 * 37 159
  89 took 4.00 (seconds)
  49G took 2.07 (seconds)

341 550 071 728 321 = 10 670 053 * 32 010 157
  89 took 110.00
  49G took 43.38

2 781 632 830 326 137 = 2 781 637 * 999 998 501
  89 took 41.00
  49G took 72.45

2^127 - 1 = 2^127 - 1
  89 took 50.00
  49G took 54.73

2^128 - 1 = 3 * 5 * 7 * 257 * 641 * 65537 * 274 177 * 6 700 417 * 67 280 421 
310 721
  89 took 220.00
  49G took 146.66

I can't exactly cite where I got this information, because the document I 
have here doesn't give any...credits...  However, it is an interesting 
comparison in speeds and capabilities between the TI-89 and the HP-49G in a 
wide variety of calculations.  If you (or anyone else) is interested, I can 
attach it to an email, or find where I originally picked up the document 
(it's in pdf format, by the way).

It does mention in the document that HP may, in a later ROM version, switch 
from BCD to binary/hex integer representation.  Apparently, the 49G is 
literally based off of CAS software written by a third-party for the HP-48 
series, and that software uses hex integers for stuff like this, so we'll 
see...

>  nah, TI probably had a list of the first 20,000 primes on AMS 1.00, then
>  decided to sacrifice mathematical speed for space on 2.03 - how else do 
they
>  free several hundred k's of mem?  =)

Hmmm...that's interesting...

JayEll