Re: TI-M: Re: TI-Math Digest V1 #22
[Prev][Next][Index][Thread]
Re: TI-M: Re: TI-Math Digest V1 #22
> Not being associated directly with the 89/92+ or m68k assembly, I don't
know
> what TI-GCC is ;) Insight?
The 89/92+ C compiler - it's sweet =)
> True; I think I was under the impression that the float vars were a set
> length, while it was the integer vars that were of varying length.
No, I was wrong - I did some more looking into it, and apparently, you're
correct - it does use separate decimal and integer representations
internally. Wonder why I never saw that in Garrett's documentation. . .
> I mean, don't the IEEE specs apply to
> binary floats, not BCD?
Yeah, IEEE is binary floats. I've never seen how those work; I just know
they're not necessarily precise.
> I'm not sure what you mean exactly; if you want to trial-divide by only
> primes, you'd either have to have the list handy (which could get pretty
> bloated) or create it on the fly with maybe a "seeve of esarathus" (not
sure
> on the name) method (which would take quite a long time if you create up
to
> sqrt(N) if N was large). Wheeler factorization has its advantages in that
it
> provides for a compact way for primality testing and proving/disproving,
> since you don't need any large and elaborate lists, just a relative small
> congruency list.
I'm thinking keep a small list for quick factorization of small numbers, and
use wheeler if you need to find larger factors. I think that would provide
a great speed boost overall without compromising size too much.
> Well, there would be (I'm guessing) about 400 primes up through 2310,
because
> I know that a probable-prime list through to 2310 is 480-something in
length.
> So a prime list up to this point isn't too bad, and that would cover
> primality-proving all numbers up through 2310^2 = 5 336 100.
Then, if you're trying to find factors larger than 2310, it's as simple as
taking the number mod 2130 and doing a binary search through the primality
list to see if that number's in there. If so, then we start testing all the
probable primes up to sqrt(num). . .
Speaking of which, I was confused on why it's num^2 for a minute - until I
realized that if we have any factors left, there can only be one that's less
than sqrt(num), so it must be prime. . .
> These results, to say the least, aren't surprising; you have to remember
that
> you only have to trial-divide up to sqrt(N). To primality prove 7919, a
> program needs only to trial-divide primes or probable-primes up to
> int(sqrt(7919)) = 88. Similarly, to primality prove 10 479, the function
> would only have to trial-divide up to 102
I see, didn't realize that before =)
> although I find it hard to believe
> that 7919 is the 1000th prime and 10479, less than 3000 more than 7919, is
> the 10 000th prime (meaning there's 9000 primes in a set of 3000
> numbers)...did you forget a digit in there?
I think I did, considering that's more primes than there are numbers =) I
lost the page that had that, so I won't worry about it now. . .
> Number Prime6 Prime6B
> PrimeASM
> - ------------ -----------
ugg, this lines up horribly! You don't use arial for email, do you? Use a
monospaced font!
> 17439280249 (=55511*314159) 5 min 5 sec 4 min 13 sec 1 min 28 sec
My TI-89, Hardware Version 2.00, AMS 2.03: 2.78 seconds =)
> As a side note, as an accuracy test, PrimeASM took just 6hr57min to find
the
> first factor of 9 876 511 069 135 577 ( = 9 876 511 * 1 000 000 007),
which
> means it trial-divided every probable-prime up to almost 10 000 000 in
about
> 7 hours. I figure that equates to about 100 trial-divides per
second...not
> that bad for a Z80 ;)
It looks like finding the first factor is only a few minutes shorter than
finding them both
LOL, my 89 does it all in 34.19 seconds =)
> Strange that it took nearly 3 min to pick up the factor 601...
No, it doesn't display any of the factors till it's done. It picked up 601
but kept trying for a long time to find more.
> True, using simply a graphing calculator for finding large primes is
stupid,
> but that doesn't take the fun out of it ;)
True =)
> Just do a binary division and check the remainder to see if the divisor is
a
> factor or not of the dividend. Subtraction would take far too long...
Got any binary multiplication/division algorithms?
> Anyway, I'd be interested in how TI factors; I doubt that the 89/92+ uses
> wheeler factorization... I think I read this off of STL's documentation
of
> Prime6, but doesn't the factor function only catch factors up to 65535?
No, it catches much larger than that. It nails 131074 instanly as 2*65537.
My only guess is that there's another algorithm, or some of that 2 megs of
Flash ROM is devoted to a prime list and wheeler is used afterwards. . .
-Scott
References: