FA+
Shop
Factoring revisted
9 years ago
Previous Journal http://www.furaffinity.net/journal/5101488/
I've had a lot of time at my new job just to sit and think. So I've been going back and looking at my factoring method. I've realized its best ran in binary versus Decimal or Hexadecimal. I've been looking into various optimizations on that as well. The first being keeping track of the combined length of the possible factors. The number of digits in A + the number of digits in B can not be larger then the target. There needs to be three types of searched a standard one, one to prevent searching mirrored pairs (11 X 01 and 01 X 11) and one to forcing leading zeros when a factor reaches half the length of the target.
Making a distributed application out of this is getting interesting. The whole of the system is a tree search. A climber goes up a known branch, calculates if there are and branches coming off of it. If there is just one it climbs it and starts again. If there is more then it needs to choose one to climb and store the rest.
The question is how often should these branches be sent back to the server. If I send them immediately it takes more bandwidth, the sever would have an easier time sorting and when the climber gets as high as it can it will have to ask the server for a new branch.
I could have the climber hold on to a couple of hundred branches and only send the lowest priority ones if it ends up with to many. Lets say It stores up to 150 when it reaches that it sends the lowest 50 back to the server then keeps going.
The last option is just have it run for so long and submit all of its branches and ask for a high priority one. It wouldn't use as much bandwidth but the information coming into server would need to be sorted in. Sorting it isn't all that hard you look at the level the branch is at and add it to that array.
On top of all this is I need to work out what system to distribute the calculation on. If I rent CPU time from Amazon or Google there is a different approach then if I just pool together the CPUs I have access too. I should mention I have 96 cores worth of high power CPUs sitting behind me in unopened boxes.
Right now I am looking in to doing all of this using Python.
I've had a lot of time at my new job just to sit and think. So I've been going back and looking at my factoring method. I've realized its best ran in binary versus Decimal or Hexadecimal. I've been looking into various optimizations on that as well. The first being keeping track of the combined length of the possible factors. The number of digits in A + the number of digits in B can not be larger then the target. There needs to be three types of searched a standard one, one to prevent searching mirrored pairs (11 X 01 and 01 X 11) and one to forcing leading zeros when a factor reaches half the length of the target.
Making a distributed application out of this is getting interesting. The whole of the system is a tree search. A climber goes up a known branch, calculates if there are and branches coming off of it. If there is just one it climbs it and starts again. If there is more then it needs to choose one to climb and store the rest.
The question is how often should these branches be sent back to the server. If I send them immediately it takes more bandwidth, the sever would have an easier time sorting and when the climber gets as high as it can it will have to ask the server for a new branch.
I could have the climber hold on to a couple of hundred branches and only send the lowest priority ones if it ends up with to many. Lets say It stores up to 150 when it reaches that it sends the lowest 50 back to the server then keeps going.
The last option is just have it run for so long and submit all of its branches and ask for a high priority one. It wouldn't use as much bandwidth but the information coming into server would need to be sorted in. Sorting it isn't all that hard you look at the level the branch is at and add it to that array.
On top of all this is I need to work out what system to distribute the calculation on. If I rent CPU time from Amazon or Google there is a different approach then if I just pool together the CPUs I have access too. I should mention I have 96 cores worth of high power CPUs sitting behind me in unopened boxes.
Right now I am looking in to doing all of this using Python.
