Eros,
For these commands to work you would need that gigantic primes file. For all 32-bit primes it's 98.2 megabytes. Zipped it's still well over 80 megabytes so including it in a thinBasic...
Type: Posts; User: Johannes; Keyword(s):
Eros,
For these commands to work you would need that gigantic primes file. For all 32-bit primes it's 98.2 megabytes. Zipped it's still well over 80 megabytes so including it in a thinBasic...
PowerBASIC does generate pure machine code, and very efficient machine code at that. And don't forget that the only reason that I managed to get this speed was to use a gigantic amount of memory. I...
7196
And the primes check out. All 203,280,221 of them. Times are in seconds.
I'll whip up a thinBasic include script that can use that 98.2-MB file. IsPrime, NextPrime, PrevPrime, NthPrime,...
By now my program has determined the primes up to 700 million, one-sixth of the entire work load. Total running time up to now somewhere around 20 or 30 hours. The checking slows down proportional to...
This is ridiculous.
'----------------------------------------------------------------------------
' !Primes10M
'
' Calculate primes up to 10 million.
'
' ©2011 Johannes...
Ah! That's a different kettle of fish. :)
You're doing a sieve, presupposing 10,000,019 as a limit. In thinBasic it took me 11.88 seconds and that includes keeping a tally of the number of primes...
I've got it down to 5m49s now (for the primes up to 10 million) and I'm guessing that's it for straight-up thinBasic.
I removed the need for an SQR in the main calculating loop, replacing it by...
Six minutes flat. (A lie: it was 6m01s.) And not a single assembler command; it's all in standard thinBasic.
I'm using the storage method as described above, with the first six primes assumed (2...
The bastards. :D
Come up with an algorithm to factor a composite integer in linear time and they'll create an award for the occasion.
About storage of primes, there are very efficient ways.
...
As it stands now, the best algorithm to factor large numbers is the General number field sieve.
If you developed an algorithm to do it in polynomial time you'd get the Nobel Prize in mathematics,...
That's an average of almost 10 bytes per prime. Does Racket store integers (or numbers in general) as decimal ASCII?
I have to say I'm very impressed with Racket's code density. I have a little...
Not when I looked at the page.
The time stamp for the current list, with "my" number being #5552 is
That looks like a time for the US continent. When I looked at the list it was 11am in Paris. ;)
Two thousand seven hundred and nineteen seconds. And the number is prime with a certainty of at least 99.9%.
Dan, most likely Racket is running into memory problems with the larger numbers. I...
I'm running #5551 ((2^10211-1)/306772303457009724362047724636324707614338377) with 3,030 digts now. The calculation of the number itself took almost no time at all. The Miller-Rabin test is......
Oh snap! :D
Should have seen that.
I was wondering what you were doing there and then I thought to check Wikipedia to see what the reliability was. Amazing that with only 5 random tries you...
Dan, remember this one?
Factoring is still "impossible" but with the Miller-Rabin test it takes about half a second on my system to determine that that number is, in fact, composite.
Dan,
My program (below) agrees with all of your checks. What is striking is that my script is much faster for the first examples, performs about equally for the 200-digit numbers, and is...
This is what I whipped up so far. I'll include it in the next release of BigInt, as examples of what you can do with BigInt, but I reserve the right to not support any of this. I will certainly not...
While testing the fixed-point stuff I saw that F(65) has '65' as its last two digits. And of course F(0)=0 and F(1)=1.
Uses "Console"
Module "BigInt"
Alias String As BigInt
BigInt a
String...
Nearly had a heart attack just now. I'm working on a fixed-point arithmetic include script for BigInt and was writing an example script with some, erm, examples.
After the simple, boring, stuff I...
Absolutely correct. A googol, defined as 10^100, is already an astounding number. The estimated number of atoms in the universe is 10^80. The factor between the two is not 20, as many...
Answer to your first question: yes. Every single encryption scheme that is half decent uses the product of (at least) two very large prime numbers. If there was a way to factor that product...
Dan, I was thinking much the same. Calculating a 125-bit next prime in zero seconds is too fantastic for words. You still have to try to factor the number to be absolutely certain and I can't see how...
Zak,
I'm a little suspicious of the execution time given for the NextPrime. The first time, zero seconds, is logical if the internal timer hasn't had time to progress. But a time in the order of...
Dan,
Between fib(100,000) and fib(1,000,000) you have a time factor of 176. When I do the same with BigInt I get a factor of 107. I'm very impressed with Racket since that's an all-purpose...