« previous next »
Pages: [1]   Go Down

Author Topic: Prime Tester benchmarks  (Read 2190 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Prime Tester benchmarks
« on: September 18, 2011, 11:05:47 am »
I was curious about what makes for a worthy enough prime tester to upload to TICalc. I think speed, RAM usage, and method are all key. The fastest version I have so far is 89 bytes, tests for primality in numbers greater than 5, and so uses a list of {2,3,5} to make sure it is not any of those. It takes 30 seconds to say 90000049 is prime and 103 seconds to say 1166881097 is not prime (this is 77477*15061). I am sure it could be faster and smaller, so any ideas?


90000049,prime,30 seconds,uses only A and Ans,89 bytes
90000049,prime,50 seconds,uses only A and Ans,65 bytes
90000049,prime,104 seconds, uses A and Ans,46 bytes
1166881097,Composite,103 seconds, uses A and Ans,89 bytes
Logged

Offline boot2490

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 607
  • Rating: +54/-36
    • View Profile
    • Boot2490's Stuff
Re: Prime Tester benchmarks
« Reply #1 on: September 18, 2011, 12:40:03 pm »
Assembly or axe? That sounds about basic speed.
Logged
I'm not worried about SOPA creating censorship, that will not stand for long. I'm worried that they'll succeed in stopping piracy!

Spoiler For Signature, updated march 23, 11:28 PM EST:















An useful tool!

PM me if you need some help. I am glad to be of assistance and part of the TI Communnity.

Offline sqrt(Time)

  • LV2 Member (Next: 40)
  • **
  • Posts: 37
  • Rating: +4/-0
    • View Profile
Re: Prime Tester benchmarks
« Reply #2 on: September 18, 2011, 02:17:44 pm »
Considering he said it uses "A and Ans", it definitely sounds like BASIC. Which makes this whole thing rather awkward considering you could probably get an order of magnitude faster or something by using ASM. Not to mention, you could get some pretty fancy-schmancy arbitrary size factoring... (AKS anyone?)  <_<
Logged

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Prime Tester benchmarks
« Reply #3 on: September 18, 2011, 02:18:59 pm »
I would use AKS, but unfortunately that wouldn't work for large numbers on the calc :D

EDIT: Still, it might be neat to implement it, even if it couldn't test large numbers...
EDIT2: Also, yes, this is BASIC... I know I made a tester in Grammer code that could test up to 65535 and it was pretty dang fast
« Last Edit: September 18, 2011, 02:22:37 pm by Xeda112358 »
Logged

Offline sqrt(Time)

  • LV2 Member (Next: 40)
  • **
  • Posts: 37
  • Rating: +4/-0
    • View Profile
Re: Prime Tester benchmarks
« Reply #4 on: September 18, 2011, 03:03:50 pm »
Well, there are several arbitrary precision systems; and I don't really know anything about AKS beyond that it's polynomial time in the number of digits, but looking at the Wikipedia article it looks all you need to implement are arbitrary size addition, subtraction, and multiplication?
Logged

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Prime Tester benchmarks
« Reply #5 on: September 18, 2011, 04:37:41 pm »
Well it is technically Polynomial time, but the issue is that even though it is polynomial time, it isn't that much faster than using an elliptic curve approach. The only difference is that using elliptic curves will result in a probabilistic result as opposed to a deterministic result (I believe). I haven't read much on elliptic curves, and I've never really implemented the AKS primality test :/
 
« Last Edit: September 18, 2011, 04:38:05 pm by Xeda112358 »
Logged
Pages: [1]   Go Up
« previous next »