Prime Factorization

[doddy1985]

I don't have any src code yet, but just thought I'd put the idea out there..

I think parallell processing could handle this pretty well (and it would be interesting to see how one could implement scaling when additional resources are added):

Given some Composite number C

HOST
do
set x = sqrt(C); floor x (or ceiling maybe??) //all numbers below repeat above sqrt(C)
send x to all e-cores.
wait for prime factors to come back in memory

ECORES
get x
(this part i'm not sure how would happen yet)
Split up the number line from 2->x (integers only) for n number of cores
each core check divisibility of all 6K+/-1 in the selected range for C //all primes of the form 6K+/-1
if a hit found; write value to memory for HOST to pick up.


Example would be like C = 101*23 = 2323 (small composite number)
sqrt(C) = 48.19....
x = 48 (floor result)
wait for ECORE results (interrupt/loop to look at memory)..

ECORES
core0 get x, C
core0 tell core1-coreM value of C
core0 tell core1-coreM here is your range to look at: //(assume M=15 for 16 core board)
core0 range 3->5
core1 range 6->9
core2 range 10->12
...
core15 range 45->48

Each ECORE (1->M):
accept range from ecore0
create array in range for the form 6*k+/-1
C mod (i) // pointer i iterates through array
if value at array(i) ==0, you have a hit.. pass value to HOST.

Could do some other stuff like.. if you know it is a semi-prime, once you get a hit just kill all other processes (you've found the ONLY lower prime factor value)


I dunno, poke fun if you wish


edit1 6/11/2014: it's def floor not ceiling

[over9000]

[doddy1985]

Oh wow (about the mersenne prime). You aren't from Missouri are you?

Yes this is for factorization (not sieve), so sieve indeed would be a different algorithm. Although.. it would be interesting just running a sieve up to sqrt(C) and save to memory (or file on hard disk) and then just check all those primes for factorizing. I guess that'd be a different approach.

I do believe this is a wheel. Although I figured there can be a bit of optimization (stuff like, check to see if the last integer in a number is 5/0) I figured i'd just start the wheel at 7 also (never look at an even composite) and divisible by 3 is an easy check (sum of integers is divisible by 3). So some of those easy cases just bump them off as one comes across them.

The wheel size also I was thinking for scalability in the future (but 16 to start):
Check to see how many resources are available, ie: if it's a cluster then programmatically determine how many cores available to work with and make the wheel size = num_cores

something like that I guess. Just figured I'd start spitting out some garbled mess on the forum, see what comes of it. It's def something I will program myself to get familiar with the SDK and epiphany chips, but if there is interest with anyone else, I'd love to see what people come up with.

[over9000]

[xilman]

[doddy1985]

Maybe the sieve would make more sense in the long run.. I was really only thinking for smaller numbers (even less than 40 bit ints). I guess I just wanted to learn how to use the ephiphany chip first before really concentrating efforts on a more advanced algorithm. This algorithm seemed simple enough at least in the beginning just to start thinking parallel. Very intersting comments though from both of you. I'll certainly keep your feedback in mind when the time comes to come up with a more practical solution for doing some heavy lifting.

best,
~doddy

[xilman]

[over9000]

[xilman]

[webmasterpdx]

I've done this before on a cray machine with 64 processors. I was interested at the time in the number of primes between powers of 2.
The determination of whether a number is prime is pretty quick. I found it best to assigm that to a simple C thread and get it assigned to different processors for different integers.
The problem I ran into is where you run out of bits for the integers.

Soooo.....what would be very useful for this kind of stuff is providing libraries for expanding bitwidth integers for when you get greater than 2 to the power of 32.... i.e. Then you'll need to do 64-bit arithmetic using 2 cores at a time, and then eventually using 3 cores at a time as the integers get bigger and bigger. Alternatively could have each core handling the higher resoluion so you have 64 cores doing 64-bit and then 96-bit and eventually 128-bit as the integers get bigger.

I think having the same thing for floating point could be very useful too, so that we could calculate pi to a large number of places......beat the record....