Nice! One suggestion: allow the viewer to input a number to view directly its factorization instead of having to wait until that number is reached - although it may not be efficient if the program caches the prime numbers and factorizations. Which brings me to my second question: is the code available somewhere? The website uses a minified version of the js code. Not the most pleasant to understand the algorithm.
> although it may not be efficient if the program caches the prime numbers and factorisations
If you watched this website non-stop for a whole year, it would still only take a thousandth of a second or so to factorise the highest number you'd reach, from scratch. Integer factorisation is only time consuming when the numbers are really really big.
which was factored in 1991, so I bet you can get the right hardware and software to factor your number too. Maybe one of these implementations will do it:
Wow -- I'm impressed. I just threw that out there to show how hard factoring is -- I didn't think anyone would actually do it. Ummm... Do you work for the NSA?
I don't work for the NSA—I just have a laptop, and a copy of Mathematica. The factorization took about 10 seconds.
Mathematica is really a pretty remarkable piece of software. I doubt it's world class for factorization, but it gives you easy access to a lot of pretty darn good algorithms for a wide range of problems.
There's 1 sentence on the implementation of FactorInteger in the docs, FWIW:
OK, so take a 64 bit integer. That's the typical size of an integer in a modern programming language. A signed integer can represent 2^63-1 which is 9223372036854775807.
Imagine a "big integer" which is a composite of multiple 64-bit integers. With a big integer made up of two regular integers, you can represent the value 170141183460469231731687303715884105727. With three, you get to 3138550867693340381917894711603833208051177722232017256447 if I'm doing the math right. That's already in the ballpark of the number you mentioned - just three regular integers together.
Granted, I'm not talking about how difficult the factoring is, but it's worth noting that the size of the numbers are pretty small to a computer. Modern computers are really fast and can brute force a large number of computations. Mathematica probably has a fairly optimized general purpose factoring algorithm as well.
A number like this might be more difficult to factor:
I would say factorisation is more tedious than hard. Modern computers can perform several billion operations per second. The simplest algorithms take O(N) time, that is to factorise N, you need to perform around N calculations. There are better algorithms which run in logarithmic time, so you only need log(N) calculations (and some which are better than that). Even with what you and I think of as big numbers, this is fast.
You get problems with numbers over 100 digits. I recently entered a challenge where one of the questions involved prime factoring a 130 digit number. That was a record feat a couple of decades ago, now it takes a day or two on a modern computer.
Anyone care to elaborate on the downvote? Given that the parent seemed surprised that it was possible to factorise a 'big' number quickly on a modern PC, I thought I'd elaborate.
Brute force search is O(N), the sieve of Eratosthenes is O(N log(log(N))). The Quadratic sieve is good up to 100 digits and runs in O(exp(sqrt(log n log log n))). Some utilities you can use for this are YAFU, MSIEVE or GGNFS.
Because of the prime numbers! I always thought of them as ugly but they are actually the _complete_ numbers, which have to be represented in those beautiful circles :)
You sound a little demanding when you capitalize "NOT" like that.
I didn't make the visualization but I find the circles to be a good choice. Not only is it pretty, it makes use of two-dimensional space in a consistent way. A factor of 5 has the same shape whenever it appears.
If you factorized things into a straight line, do you just line everything up horizontally, in which case you just see hundreds of dots with gaps in them and there would be nothing interesting about the visualization? Or do you make rectangles, with some of the factors going vertically? In that case, sometimes your 5s will go horizontally and sometimes they'll go vertically, making a distinction out of nothing.
I think this actually wasn't an arbitrary choice, but a result of the algorithm.. e.g. factors are displayed as clusters ordered in a circle (factors of 2 is a circle with groups of 2, factors of 3 is a circle of groups of 3).
They aren't circles, they are p-gons. A factorization is drawn as a tree where each level has p radially symmetric branches, corresponding to a prime factor p. (Only the leafs are drawn, but you can fill in the branches and node). A prime number has only one level
Totally out of left field here, but I got some auditory synesthesia from watching this, especially on high speed. If any of you did as well and are interested why, it's probably the same phenomenon talked about here: https://www.newscientist.com/article/dn14459-screensaver-rev...
31 comments
[ 1.1 ms ] story [ 68.2 ms ] threadIf you watched this website non-stop for a whole year, it would still only take a thousandth of a second or so to factorise the highest number you'd reach, from scratch. Integer factorisation is only time consuming when the numbers are really really big.
https://en.wikipedia.org/wiki/RSA_numbers
which was factored in 1991, so I bet you can get the right hardware and software to factor your number too. Maybe one of these implementations will do it:
https://en.wikipedia.org/wiki/General_number_field_sieve#Imp...
651651626268416641641703*983764598769387649827639876407 = 641071800653367850802176606120792275422168080497001121
Mathematica is really a pretty remarkable piece of software. I doubt it's world class for factorization, but it gives you easy access to a lot of pretty darn good algorithms for a wide range of problems.
There's 1 sentence on the implementation of FactorInteger in the docs, FWIW:
http://reference.wolfram.com/language/tutorial/SomeNotesOnIn...
641071800653367850802176606120792275422168080497001121
OK, so take a 64 bit integer. That's the typical size of an integer in a modern programming language. A signed integer can represent 2^63-1 which is 9223372036854775807.
Imagine a "big integer" which is a composite of multiple 64-bit integers. With a big integer made up of two regular integers, you can represent the value 170141183460469231731687303715884105727. With three, you get to 3138550867693340381917894711603833208051177722232017256447 if I'm doing the math right. That's already in the ballpark of the number you mentioned - just three regular integers together.
Granted, I'm not talking about how difficult the factoring is, but it's worth noting that the size of the numbers are pretty small to a computer. Modern computers are really fast and can brute force a large number of computations. Mathematica probably has a fairly optimized general purpose factoring algorithm as well.
A number like this might be more difficult to factor:
http://pari.math.u-bordeaux.fr/
The relevant file is
You get problems with numbers over 100 digits. I recently entered a challenge where one of the questions involved prime factoring a 130 digit number. That was a record feat a couple of decades ago, now it takes a day or two on a modern computer.
Brute force search is O(N), the sieve of Eratosthenes is O(N log(log(N))). The Quadratic sieve is good up to 100 digits and runs in O(exp(sqrt(log n log log n))). Some utilities you can use for this are YAFU, MSIEVE or GGNFS.
//Link to original minified source code http://www.datapointed.net/media/2012/10/factor_min.js
//Credits to Stephen Von Worley www.datapointed.net
Here there is an expanded version https://gist.github.com/brianahearn/6032808 and a discussion: https://groups.google.com/forum/m/#!msg/mathfuture/yEfAaey6j...
http://mathlesstraveled.com/2012/10/05/factorization-diagram...
(from the "About" page)
I didn't make the visualization but I find the circles to be a good choice. Not only is it pretty, it makes use of two-dimensional space in a consistent way. A factor of 5 has the same shape whenever it appears.
If you factorized things into a straight line, do you just line everything up horizontally, in which case you just see hundreds of dots with gaps in them and there would be nothing interesting about the visualization? Or do you make rectangles, with some of the factors going vertically? In that case, sometimes your 5s will go horizontally and sometimes they'll go vertically, making a distinction out of nothing.
So for primes, you have a circle of groups of 1.