Search:

Type: Posts; User: Johannes

Page 1 of 5 1 2 3 4

Search: Search took 0.00 seconds.

  1. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    Eros, For these commands to work you would...

    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...
  2. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    PowerBASIC does generate pure machine code, and...

    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...
  3. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    7196 And the primes check out. All 203,280,221...

    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,...
  4. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    By now my program has determined the primes up to...

    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...
  5. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    This is ridiculous. ...

    This is ridiculous.

    '----------------------------------------------------------------------------
    ' !Primes10M
    '
    ' Calculate primes up to 10 million.
    '
    ' 2011 Johannes...
  6. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    Ah! That's a different kettle of fish. :) ...

    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...
  7. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    I've got it down to 5m49s now (for the primes up...

    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...
  8. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    Six minutes flat. (A lie: it was 6m01s.) And not...

    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...
  9. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    The bastards. :D Come up with an algorithm to...

    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.
    ...
  10. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    As it stands now, the best algorithm to factor...

    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,...
  11. Thread: Factoring 1

    by Johannes
    Replies
    22
    Views
    13,758

    That's an average of almost 10 bytes per prime....

    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...
  12. Replies
    15
    Views
    14,596

    Not when I looked at the page. The time stamp...

    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. ;)
  13. Replies
    15
    Views
    14,596

    Two thousand seven hundred and nineteen seconds....

    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...
  14. Replies
    15
    Views
    14,596

    I'm running #5551...

    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......
  15. Replies
    15
    Views
    14,596

    Oh snap! :D Should have seen that. I was...

    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...
  16. Replies
    15
    Views
    14,596

    Dan, remember this one? Factoring is still...

    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.
  17. Replies
    15
    Views
    14,596

    Dan, My program (below) agrees with all of...

    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...
  18. Replies
    2
    Views
    6,440

    For the fractionally inclined

    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...
  19. Replies
    14
    Views
    14,246

    Funny Fibonacci numbers

    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...
  20. Replies
    2
    Views
    6,440

    May Charles Babbage watch over my poor, poor heart.

    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...
  21. Replies
    14
    Views
    14,246

    Absolutely correct. A googol, defined as 10^100,...

    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...
  22. Replies
    37
    Views
    21,736

    Answer to your first question: yes. Every single...

    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...
  23. Replies
    37
    Views
    21,736

    Dan, I was thinking much the same. Calculating a...

    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...
  24. Replies
    37
    Views
    21,736

    Zak, I'm a little suspicious of the execution...

    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...
  25. Replies
    14
    Views
    14,246

    Dan, Between fib(100,000) and fib(1,000,000)...

    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...
Results 1 to 25 of 101
Page 1 of 5 1 2 3 4