Javascript Factorization App

Below is an interactive Javascript-driven app for factoring numbers based on an algorithm I call "shifting parabola". It can factor most numbers up to a billion; beyond that the algorithm suffers from lack of precision math issues (and computational complexity issues).

Enter a number up to around a billion. It and the following 10 numbers will be factored for you. If the script encounters an out-of-range calculation however, it may eat up javascript cpu, requiring a cancel.

Calculations can be verified here.

The script may generate numbers with decimals, these are a result of floating point math errors. I did try it on a javascript large-integer math library, but that turned out to slow down calculations to such a degree that performance became worse for numbers of the same size.

Erlang Factorization Code

An Erlang version of this program is available here - it can handle at least twice the number of digits. Erlang, a hybrid of Prolog, has a built-in integer type that handles basic big integer math (only limited by memory). It doesn't have built-in bigint square root or power functions so those were added . The script factors some numbers up to 20 digits very quickly; others can take say 10 minutes to factor on an Intel i7 computer. E.g.

c(factor).

factor:fac(10400513711337). %quick

[23,3,3,[3],"^2",16748009197]

factor:fac(12114335562531336337). %slow

[7,241888949,43,131,1270123]

I have no idea at moment how it compares to number sieve and other approaches.

Factorization Explanation

I'll try to do a better job of explaining it soon, but for now suffice to say it involves a way of searching for factors in cartesian number space by finding any fractions that lie on the line y = N-x that intersect a series of inverted (x^2) parabolas whose vertices intersect y=x^2. Each such fraction points to a factor.

In math-speak normally we percieve fractions in cartisian space as the enumeration of points on lines of different slopes y/x= {1,2,3 ... infinity} beginning at (0,0): e.g. series

(0,0) (1,1) (2,2) (3,3) ...

(0,0) (1,2) (2,4) (3,6) ...

(0,0) (1,3) (2,6) (3,9) ... etc.

Or you could count them vertically,

(1,0) (1,1) (1,2) (1,3) (1,4) ...

(2,0) (2,2) (2,4) (2,6) (2,8) ...

(3,0) (3,3) (3,6) (3,9) (3,12) ... etc.

But there seems to be no pattern here from one slope or column to the next - and that's why factoring is so tough. One can't tell whether any coordinate related to N will yeild a fraction without actually dividing by the x or y axis of that coordinate.

However, these very same fractions can be counted as points on inverted parabolas that each have a vertex on y=x^2 :

vertex | series |
---|---|

(0,0) | (0,0) |

(.5,.25) | (0,0) (1,0) |

(1,1) | (0,0) (1,1) (2,0) |

(1.5,2.25) | (0,0) (1,2) (2,2) (3,0) |

(2,4) | (0,0) (1,3) (2,4) (3,3) (4,0) |

(2.5,6.25) | (0,0) (1,4) (2,6) (3,6) (4,4) (5,0) |

(3,9) | (0,0) (1,5) (2,8) (3,9) (4,8) (5,5) (6,0) |

(3.5,12.25) | (0,0) (1,6) (2,10) (3,12) (4,12) (5,10) (6,6) (7,0) |

(4,16) | (0,0) (1,7) (2,12) (3,15) (4,16) (5,15) (6,12) (7,7) (8,0) |

... | ... |

You may say "whuuut?". This seems like a really complicated way to organize fractions. But there are patterns here now.

Explanation Part 2

Points on all such parabolas become a set of cascading fractions to navigate through in search of our y = N-x intersection points. To put it literarily, this creates a parabolic geography that has deserts that we can skip in the search for our fractional oases.

The interactive diagram below should help to make this case. You can click on a point on the x or y axis to identify a number N that you want to factor. The y=N-x line will be drawn, and all points that fall exactly on it are factors. As well you can click on or off a variety of lines and parabolas to see which factors intersect with them. Clicking on a factor will focus a cursor there and indicate the (x,y) coordinate of that factor.

*Note: This graphic presentation is currently not compatible with Microsoft IE due to a small bug in the Rafaeljs graphics library which hopefully will be fixed soon.*

Here are a few toggles which will superimpose slope lines, vertical lines, a graph of y=x^2, slope lines eminating from selected number to be factored, and various inverted parabolas:

Slope Vertical x^2 Symmetry Parabola/1Ways of enumerating fractions in cartesian space.

aka. *The wings of Icarus*

more algorithm description coming soon ...

Factor Javascript

/*************************************************************************************************** Copyright 2008 by Damion Dooley Cannot be reproduced for publication without permission ****************************************************************************************************/ function factor(n) { if (n < 4) { return n; } if (isEven(n)) { return "2 " + factor(n / 2); } var uroot = Math.ceil(Math.sqrt(n)); var ubound = Math.pow(uroot, 2); var m = ubound - n; if (m == 0) { var f = factor(uroot); return f + (" " + f + " "); } else { var uroot2 = 2 * uroot; var count = 0; var displace = 0; var y; var yh; var c1; var skip = 0; while (count < ubound) { y = Math.sqrt(m + displace); if (parseInt("" + y) == y) { var factor1 = uroot - y + count; if (factor1 == 1) { return n + " "; } var factor2 = n / factor1; return factor(factor1) + (" " + factor(factor2) + " "); } yh = Math.ceil(y); c1 = Math.floor((m - Math.pow(yh - count, 2)) / (2 * (yh - count - uroot))); if (c1 > count) { skip += c1 - count; count = c1; displace = count * uroot2 + Math.pow(count, 2); } else { count++; displace = displace + uroot2 + 2 * count - 1; } } } return n + " "; }