Closed modrobert closed 5 years ago
Thank you for your kind words. We are pleased that people find calc useful.
p.s. Tomorrow (Oct 30) is the 40th anniversary of my co-discovery that 2^21701-1 is prime. While this pre-dates calc by 20 years, it is fun to see what calc can do today. Try:
calc -D :0 'read lucas; if (lucas(1, 21701)) { print "2^21701-1 is prime"; }'
It took the CDC Cyber 174 over 7 hours and 40 minutes to perform the above calculation in 1978. You time may be a bit faster. :-)
Happy anniversary!
Yes, it went a bit faster for me (although this PC laptop is pretty far from high end):
$ time calc -D :0 'read lucas; if (lucas(1, 21701)) { print "2^21701-1 is prime"; }' 2^21701-1 is prime
real 0m10.820s user 0m10.819s sys 0m0.000s
I have an Amiga 1200 in my "lab" with 68030 @ 33MHz and 128MB RAM, but might be a bit hairy to compile the calc source code on it, it's AmigaOS 3.1, would probably get closer to your result time wise though. ;)
Almost forgot, have my own rather ugly prime hack here: https://github.com/modrobert/primecheck
It's x86 assembler mixed with C, limited to 64bit, hehe.
On a MacBook Pro (Retina, 15-inch, Mid 2015):
$ time calc -D :0 'read lucas; if (lucas(1,21701)) {print "2^21701-1 is prime";}' 2^21701-1 is prime
real 0m2.131s user 0m2.117s sys 0m0.007s
I just pasted 2^21701-1 into 'calc' to get several pages of integer in the terminal, didn't realize how big that number was at first glance.
Reading the comments in the 'lucas.cal' script now, what kind of black magic algos are at work here I wonder. ;)
For a tutorial on what lucas.cal is doing, see:
http://www.isthe.com/chongo/tech/math/prime/prime-tutorial.pdf
Thanks, will read that.
Have to admit, I'm kind of slow at math, but make up for it by being stubborn and having a knack for reverse engineering other peoples code.
Thinking of reverse engineering, specifically reversing nature, as in physics, what's your take on quantum computing and its potential for finding primes?
Quantum computing best result to date is to factor the number 56153. Seriously, over the last 17 years quantum computers have progressed from being able to factor a number as large as 15, to a factoring a number as large as 56153.
BTW: proving primality by failing to factor a number (other than 1 and itself) is an extremely inefficient way to test primality. To date, inefficient factoring is the only way for a quantum computer to test for primality. This is because more modern methods of testing for primality are too complex for a quantum computer of today to perform.
When quantum computers are able to the type of primality testing I cannot do in my head, then I'll start to bother to pay more attention to the state quantum primality testing.
My guess is quantum computers being able to outperform the primality testing capability of a human who is good at doing arithmetic in their head may be just around the corner. It seems that the date when quantum computers can outperform what a human using calculator (and/or a human with pencil and paper) may be only a few years down the road.
When quantum computers are able to perform primality at a level that is even similar to the level of a classical computers, then I'll seriously look into performing some primality tests with quantum computing. But that seems well down the road as classical computers can perform more modern primality tests that trivial factoring cannot hope to perform before "the heat death of the Universe" arrives. For example, a quantum computer attempting to factor 2^21701-1 (and proving that it is prime by failing to find a factor other than 1 and itself) may take longer than the "expected useful lifetime of our Universe". For quantum computers to do primality testing that is at a similar level to classical computers will require quantum computers to be able executing algorithms that are far beyond the complexity of what appears to be possible with quantum computers today.
I will start of become impressed with quantum computers when they start to perform primality testing (or even the more trivial factoring) at a level that is difficult for a classical computer to perform.
I will be sold that quantum computer-based primality testing "is a real thing" when a quantum computer can perform a primality test that is impractical for a classical computer to perform. To quote a well-respected quantum computing researcher in Physical Review Letters: "We're still a far away from outperforming classical computers (in factoring numbers)." While there is always hope, such a day seems far off in the future without a significant breakthrough in quantum computing capability: both in computational performance as well as in quantum computing algorithm complexity.
Until then, I will simply maintain mild amusement mixed with quaint hope that quantum computing will amount to something, eventually.
Yes, even at temperatures close to zero kelvin they are struggling to keep the qubits functional long enough to perform simple calculations, once a "state machine" is rigged it starts to vanish. I think it takes a major discovery (or many small) either in error correction or coherence time before quantum computers gets useful.
In recent years there seems to be a lot more funding towards quantum computer research, I guess someone hinted it can be used to break encryption to access the deep state funds. Research efforts are increasing fast world wide.
https://en.wikipedia.org/wiki/Timeline_of_quantum_computing
I think there is potential, and personally find entanglement fascinating and mimicking nature to do things like Grover's algorithm O(√N), but have to agree we are not there yet when it comes to useful performance.
PS: Regarding the "tutorial", challenge accepted.
The tutorial does NOT require any heavy math.
OK, I was thinking about a hardware approach, using Verilog (or VHDL), read about fast multiply/add circuit needed, and "squaring by transform" FFT experimentation could be right up my alley. Biggest problem for me is completing projects, always tend to start new ones instead. ;)
Released calc version 2.12.7.0 and therefore closing this thank you comment as 'complete'.
Thanks!
Consider this "issue" positive feedback.
I've used 'calc' for years, and it's great. Easy to use, text based, intuitive, powerful, and the best part of all; it's constantly inviting to experimentation and playing around with numbers.
Big thanks to everyone involved in developing this incredible tool!