Factoring Integers
I've spent way too much time studying the factoring of integers. In many ways it was fun, and in other ways it was not. I never landed on the holy grail, but I did find a bunch of neat and awesome things. I challenged the norm. The coolest thing I found was Unbalanced Algebra.
What I'll do With It
In my mid to late 30s, I'm going to collect it all... and publish the things I've found on Arxiv.
An Example
This is a small example of a factoring program. It's not the most efficient program I've ever written... however, it would do no good to run a super efficient program in a web browser anyway.
Alternatively, this is just the most recent algorithm I wrote. Spending time piddling on it was my gift to myself for Christmas.
Interface
Factor an Interger
How it Works
The math behind this algorithm is relatively naive... however, the management of the JavaScript state and the demands/limitations of the stack frames made it more difficult.
The Math
There are basically 4 steps.
- Indexed Check: As you enter numbers, the results are saved. The first thing the algorith does is check if the number being factored has been saved.
- Small Check: If the number isn't already saved, then the first 30 primes are checked as divisors. Instead of an additive algorithm, it naively uses modulo.
- Semi-Quadratic Check: This step isn't actually a full-quadric seive. But it is an interesting and easily-implemented algorithm that eliminates factors from the squareroot downward (like a quadratic sieve).
- Brute Check: A cutoff is calculatated at the beginning of the process, and if the quadratic sieve reaches it, then the algorithm begins to just brute-force modulo up to the cutoff.
The JavaScript
Several problems had to be solved to have this in a web browser.
- Call Stack Limitations: JavaScript has a maximum call stack that is much smaller than you would encounter in other languages. Normally, you wouldn't run into problems having to do with that unless you had a bug in your program. However, in this mathematically intensive process, the call stack can get many hundreds of thousands deep if you use recursion. My solution to this was to use the function setTimeout every so many calls to create a new call stack, leveraging closure so that the new instance could see the arugments.
- Cancelable Factoring: I needed a mechanism to be able to cancel any factoring calls. To either move to a new integer or change sections. I've included 2 features to achieve this. First, I included a 'call index' in that gets incremented on every call to the function Submit. All of the meat-and-potatoes function in the class check that this value hasn't changed, and if they have, they return. Second, the function Submit also clears any timeouts set by the class before proceding with a new factoring.
- Non-Blocking Factoring: The timeouts keep the thread from being blocked. In order for the animations to continue to run smoothly, I opted for shorter calculation spurts. The timeouts give the animation time to calculate, and a window of time for the browser to process user input.
- Application Cleanup: Upon changing sections, I wanted to make sure any factoring calculation was canceled. I registered an listener with VCR.js to make sure the call index was incremented, and any timeouts were canceled. I included a flag in the class to that gets flipped on the first call to submit, so that registereing the event listener can be deferred until it is needed, and will only be set once. The flag gets unset in the listener itself.
A Clear Implementation of the Semi-Quadratic Sieve
So, if you read the JavaScript on this page, it will be all twisted up with the work needed to get this to run safely inside of a browser.
I'm pretty proud of that part of the algorithm, because of how simple it is. Here is a clear implementation in Haskel, without all of the JavaScript noise:
import Data.List
import System.IO
runnit :: Integer -> Integer -> Integer -> Integer -> String
runnit x y t n
| x <= 0 || y <= 0 = "error"
| t < n = runnit x (y+1) (t+x) n
| t > n = runnit (x-1) y (t-y) n
| otherwise = show x ++ " x " ++ show y ++ " = " ++ show n
factorit :: Integer -> String
factorit x =
let sr=sqrt(fromIntegral x)
in let bottom=floor(sr)
top=ceiling(sr)
in let tot = bottom*top
in runnit bottom top tot x
main = do
print "Enter your number: ";
numInp <- getLine
let n = read numInp :: Integer
print (factorit(n))
