Author |
Message |
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 22 Oct 2009 06:41:44 pm Post subject: |
|
|
Okay, so I have this program I wrote in java. It has a class called Node. It has it's main class. It also has a Factor class that is used with a lot of static things. The Factor program could be put into the main program, but there is still the Node object class. I don't know much about C, except I know it is a lot faster. So, I was hoping to convert it to C to make it faster.
btw, to spur some interest in this, the java program is able to find prime factors of numbers. It is just slower the longer the number is. Go figure. It's still practical, it's just that java wants to slow down on me, and I want it faster!!! I could have java run all day, and it would factor it. I just don't want to wait all day. It seems to be faster than GNFS, as far as I can tell.
Can it be programmed in C? It was hard enough to get to work in Java. C is going to be a nightmare for someone like me who doesn't know it that much. Will someone help me?
For the record, I also use the BigInteger class. The program doesn't really slow down, as much, as doesn't find suitable numbers quicker. It takes longer, and longer, and longer.
At the start, it can go through about 3,000 different number sets, per second. It then slows to about 250 per second. I just hope it can be made faster, in C. So that it may go through 30,000 per second, then 2,500 per second, and so on...
EDIT2: Now, we are at 100 per second. It just keeps slowing...
Last edited by Guest on 22 Oct 2009 06:48:59 pm; edited 1 time in total |
|
Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008 Posts: 438
|
Posted: 23 Oct 2009 03:47:23 am Post subject: |
|
|
serch the solution in a diferent algoritm, rather than a diferent langauge
yes, C (or even asm) may be faster, but it will still slow down at the same rate as java code
(well, maybe less due horribele garbage collection in java, but you get the picture...) |
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 23 Oct 2009 07:11:27 am Post subject: |
|
|
I looked over my code again, and what I did was put the code to increment the counter, inside where it finds the new possible numbers. So, it slows down to me, but in reality, it's finding less possible numbers to use.
I still think C would be better, but it works for now.
EDIT: I just increased maximum heap size. It is running a slight bit faster. It is slowing down, but only slightly. This might work!!!
wow. No wonder 10,000m didn't work. 1024m = 1 G. I only have 2 G memory. Oh well. It still hasn't slowed down yet.
Last edited by Guest on 23 Oct 2009 07:39:57 am; edited 1 time in total |
|
Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008 Posts: 438
|
Posted: 23 Oct 2009 09:01:48 am Post subject: |
|
|
well, we can test it for you, my new laptop has 4 GB
just note that rewriting something in a new language is usually a bad idea, unless you're sure your algorithm is prefect (it ain't) |
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 23 Oct 2009 09:08:11 am Post subject: |
|
|
I am currently writing it to erase the references when it uses them. It shouldn't slow down as much. I will post when I finish. |
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 23 Oct 2009 09:34:44 am Post subject: |
|
|
Okay, I figured out how to erase the references, but I'm still losing memory. I have multiple processors, and want to make use threads. Will you help Darkstone?
EDIT: Okay, I increased heap size, and it made it finish in 209 seconds. That is for a 48 bitlength number.
48 bit: 209 seconds
53 bit: 764 seconds.
60 bit: Just started.
Last edited by Guest on 23 Oct 2009 12:13:16 pm; edited 1 time in total |
|
Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008 Posts: 438
|
Posted: 23 Oct 2009 01:00:10 pm Post subject: |
|
|
well, i only know z80 and basic, so this main contain mistakes
most likely, you have a memory leak (leaks in java are very, very bad due to garbage collection, this will cause freezes and alike), these are usualy caused by:
infernor algorithms (O=n² rather than O=n or even O=log(n))
huge arrays /heaps that you resize often (hint: make all your structures fixed-size)
creating new vars, but not erasing the old var (aka: declare your cars only once, and clear then each time you start a new loop)
goto/labels
solve these first
paraellizing is pretty hard, i dont know how your code works, but i suppose you can do someting like this in the main thread
GetCounter() {
if "win condition" stop (or whatever java uses to stop / halt current thread)
counter++; //should be a global varriable of some kind
return counter
}
on the start of the program, you spawn X threads (where X is the amount of threads the processor can handle) , each thread calls GetCounter, wich return a number, tbe thread will make some calculations to make sure the number is (not) a prime/factor/whatever you want, then calls for a new number
this will increase the CPU untillization
thats basely it..
it basely works for any amount of cores (AMD has 12-threaded cores atm...) as long you can spawn that amount of threads, dont forget to use task manager to check your cpu utilization
if you cant seem to get your CPU usage higher, you probably have an i/o bottleneck , there is few you can do about this.. (other than writing it in asm because higher level programing languages do suck in memory management)
to clairify threading...:
bad:
better:
best:
|
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 23 Oct 2009 09:51:00 pm Post subject: |
|
|
The problem with the threads, is that I don't know how to do it without hard coding it. It depends on how many possible facters for the first loop. |
|
Back to top |
|
|
Mapar007
Advanced Member
Joined: 04 Oct 2008 Posts: 365
|
Posted: 24 Oct 2009 05:30:42 am Post subject: |
|
|
@Dark: Java uses a semaphore-like system for threading, so the whole counter thing is unnecessary.
@Graphmastur: You should read "Java Threads" (search on oreilly.com). It covers everything related to threaded programming. Explaining it here would be far too complicated. |
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 24 Oct 2009 06:39:09 am Post subject: |
|
|
I know how to do threads. I just don't know if I'd need 5 threads or 10 threads. I guess I could create a class, that implemented runnable. I will have to read up on synchronization, though. |
|
Back to top |
|
|
magicdanw pcGuru()
Calc Guru
Joined: 14 Feb 2007 Posts: 1110
|
Posted: 24 Oct 2009 10:00:31 am Post subject: |
|
|
I'd say you should use roughly a million threads, each performing a single bytecode operation, and sending the result through a wormhole in time back to the start of the next thread!
If only...sigh... |
|
Back to top |
|
|
GloryMXE7 Puzzleman 3000
Active Member
Joined: 02 Nov 2008 Posts: 604
|
Posted: 24 Oct 2009 10:47:13 am Post subject: |
|
|
i have no idea what a thread is, then again i only have about 31 days worth of java knowledge and im only on chapter 4 in the book I'm using for class. as for the wormhole idea science isn't ready for that quite yet. |
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 24 Oct 2009 11:13:57 am Post subject: |
|
|
magicdanw wrote: I'd say you should use roughly a million threads, each performing a single bytecode operation, and sending the result through a wormhole in time back to the start of the next thread!
If only...sigh...
Um... Yeah, the black hole used too much electricity. I settled for a tree instead... |
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 24 Oct 2009 01:26:28 pm Post subject: |
|
|
Okay, so I just threaded my application. I am getting some errors, though.
Exception in thread "Thread-2" java.lang.NullPointerException
at rsatreefactor.Factor.FindFactors(Factor.java:1
at rsatreefactor.Main$2.run(Main.java:6
at java.lang.Thread.run(Thread.java:613)
Exception in thread "Thread-3" java.lang.NullPointerException
at rsatreefactor.Factor.FindFactors(Factor.java:1
at rsatreefactor.Main$2.run(Main.java:6
at java.lang.Thread.run(Thread.java:613)
Exception in thread "Thread-4" java.lang.NullPointerException
at rsatreefactor.Factor.FindFactors(Factor.java:1
at rsatreefactor.Main$2.run(Main.java:6
at java.lang.Thread.run(Thread.java:613)
Sometimes, all 4 threads crash, and sometimes, it works perfectly. Do you need me to post code? |
|
Back to top |
|
|
darkstone knight
Advanced Member
Joined: 07 Sep 2008 Posts: 438
|
Posted: 24 Oct 2009 06:48:26 pm Post subject: |
|
|
seeing as "thread-1" doesnt throw an error, you might be using duplicate labels / vars |
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 24 Oct 2009 08:11:59 pm Post subject: |
|
|
I thought so, but sometimes, even of crashes. It seems to be where the node class has some biginteger variables that don't get declared. Except, that I made sure the variables were declared. This is why I hate threads! |
|
Back to top |
|
|
Mapar007
Advanced Member
Joined: 04 Oct 2008 Posts: 365
|
Posted: 25 Oct 2009 01:40:36 am Post subject: |
|
|
You need to make use of the semaphores. (did you have the synchronized keyword on your findFactors method and those BigIntegers?)
And can we see this line 18 causing trouble (or the whole source, if possible)
Last edited by Guest on 25 Oct 2009 01:41:11 am; edited 1 time in total |
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 25 Oct 2009 09:47:43 am Post subject: |
|
|
Sure. Line 18 is in the FindFactors program, but I erased a few comment lines, so now it is line 15. Sometimes it works perfectly and sometimes all or some of them throw an exception. Can you figure it out?
EDIT: For the record, I changed the recursive method to be synchronized.
[attachment=2877:rsatreefactor.zip]
Last edited by Guest on 25 Oct 2009 09:53:48 am; edited 1 time in total |
|
Back to top |
|
|
Lionel Debroux
Member
Joined: 01 Aug 2009 Posts: 170
|
Posted: 29 Oct 2009 08:10:48 am Post subject: |
|
|
Do you have to do this as a homework assignment, or is it purely for fun ?
As one of the admins of the BOINC server that centralized the factoring of the TI-* 512-bit RSA keys, I recently became interested in factoring integers. I learnt (without trying to understand how the ones I didn't already know about work ) that there are multiple factoring algorithms, and each of them has a range (a size, if you prefer) of input numbers where it shines. Trial division is good, but only up to 1000-10000. Then, other methods are used, such as (in ascending order of input size) Pollard's rho heuristic (easy to implement on embedded platforms), P+1, P-1, ECM, quadratic sieves (several algorithms), number field sieves (several algorithms). GNFS and SNFS are completely undesirable for 20-digit numbers, they don't start shining until they're fed 90 to 110-digit numbers (at which point the quadratic sieves become too slow).
ECM is slightly different from the others: it's great for shaving off "small" factors, thereby reducing the size of composites that are fed to other methods (if composite factors remain). There's a rule of thumb for stopping ECM work: about 2/7 of the GNFS complexity or 2/9 of the SNFS complexity.
If you're looking for some code:
* a Java applet, with available source code, can be reached at http://www.alpertron.com.ar/ECM.HTM .
* YAFU ( http://sites.google.com/site/bbuhrow/home ) implements all the algorithms I mentioned above, in C + x86,x86_64 (and others ?) assembly. Here is the output of the factoring of the three numbers found in your Main.java:
Code: >> 10234781923099*3216049751*3007
ans = 98977112540952773175735443
>> factor(98977112540952773175735443)
***** cpu looks to be about 1995.011040 MHz
factoring 98977112540952773175735443
div: primes less than 10000
rho: x^2 + 1, doing 1000 iterations on C23
rho: x^2 + 3, doing 1000 iterations on C23
rho: x^2 + 2, doing 1000 iterations on C23
starting pQS on c(23): 32915567855321840098349
s_init = 0, pmax = 1033, cutoff = 30990(30 * pmax)
inner_block_size = 32768, blocksize = 65536
n = 23 digits, 78 bits
B = 99, T = 1.10, k = 5
base closnuf = 38
167(99) relations found: 85 full + 82 from 394 partial, using 3 blocks
Total pQS time = 0.0000 seconds.
Total factoring time = 0.1108 seconds
***factors found***
P2 = 31
P2 = 97
PRP14 = 10234781923099
PRP10 = 3216049751
ans = 1
and the output of YAFU factoring a C83:
Code: >> factor(1382662627090824241033467794067341123107180168462823076114730977627871907579
7947537)
***** cpu looks to be about 1994.999520 MHz
factoring 13826626270908242410334677940673411231071801684628230761147309776278719075797947
537
div: primes less than 10000
rho: x^2 + 1, doing 1000 iterations on C83
rho: x^2 + 3, doing 1000 iterations on C83
rho: x^2 + 2, doing 1000 iterations on C83
pp1: base 3883490793, doing B1 = 20K, B2 = 1M on C83, processed < 1000003
pp1: base 415594200, doing B1 = 20K, B2 = 1M on C83, processed < 1000003
pp1: base 2427629959, doing B1 = 20K, B2 = 1M on C83, processed < 1000003
pm1: base 3544428482, doing B1 = 100K, B2 = 5M on C83, processed < 5000011
***** using 64bit linux core2 data for QS time estimation
***** qs time estimate = 1024.550603 seconds
ecm: curve 25, sigma = 3098119206, C83 input, B1 = 2K, B2 = 200K, processed < 199999
***** 15 digit level took 1.813642 seconds.
***** using 64bit linux core2 data for QS time estimation
***** qs time estimate = 1024.550603 seconds
***** estimating 90 more curves can be run at 20 digit level
ecm: curve 90, sigma = 424351559, C83 input, B1 = 11K, B2 = 1100K, processed < 1099997
***** 20 digit level took 20.925285 seconds.
***** using 64bit linux core2 data for QS time estimation
***** qs time estimate = 1024.550603 seconds
***** estimating 200 more curves can be run at 25 digit level
ecm: curve 200, sigma = 3729139555, C83 input, B1 = 50K, B2 = 5M, processed < 4999999
***** 25 digit level took 164.167254 seconds.
***** using 64bit linux core2 data for QS time estimation
***** qs time estimate = 1024.550603 seconds
***** estimating 16 more curves can be run at 30 digit level
ecm: curve 16, sigma = 1586959734, C83 input, B1 = 250K, B2 = 25M, processed < 24999983
***** 30 digit level took 58.700405 seconds.
***** using 64bit linux core2 data for QS time estimation
***** qs time estimate = 1024.550603 seconds
***** estimating 0 more curves can be run at 35 digit level
starting SIQS on c83: 13826626270908242410334677940673411231071801684628230761147309776278719075797947
537
==== sieve params ====
n = 84 digits, 277 bits
factor base: 49004 primes (max prime = 1268791)
single large prime cutoff: 120535145 (95 * pmax)
double large prime range from 42 to 49 bits
double large prime cutoff: 351564205032149
using 26 large prime slices of factor base
buckets hold 1024 elements
sieve interval: 7 blocks of size 65536
polynomial A has ~ 11 factors
using multiplier of 17
using small prime variation correction of 20 bits
using SSE2 for trial division and x128 sieve scanning
trial factoring cutoff at 93 bits
==== sieving in progress (1 thread): 49068 relations needed ====
==== Press ctrl-c to abort and save state ====
49155 rels found: 21906 full + 27249 from 288769 partial, (368.90 rels/sec)
sieve time = 418.0702, relation time = 137.5721, poly_time = 302.6278
trial division touched 5929061 sieve locations out of 32550876610560
QS elapsed time = 865.7103 seconds.
==== post processing stage (msieve-1.38) ====
begin with 310675 relations
reduce to 79044 relations in 6 passes
attempting to read 79044 relations
recovered 79044 relations
recovered 59775 polynomials
attempting to build 49155 cycles
found 49155 cycles in 3 passes
distribution of cycle lengths:
length 1 : 21906
length 2 : 19701
length 3 : 5463
length 4 : 1581
length 5 : 381
length 6 : 100
length 7 : 16
length 9+: 7
largest cycle: 8 relations
seed1 = 3523621745, seed2 = 387981122
matrix is 49004 x 49155 (8.0 MB) with weight 1697406 (34.53/col)
sparse part has weight 1697406 (34.53/col)
filtering completed in 4 passes
matrix is 37429 x 37493 (6.4 MB) with weight 1390581 (37.09/col)
sparse part has weight 1390581 (37.09/col)
saving the first 48 matrix rows for later
matrix is 37381 x 37493 (5.5 MB) with weight 1165543 (31.09/col)
sparse part has weight 1078663 (28.77/col)
matrix includes 64 packed rows
using block size 14997 for processor cache size 4096 kB
commencing Lanczos iteration
memory use: 4.9 MB
lanczos halted after 593 iterations (dim = 37381)
recovered 18 nontrivial dependencies
Lanczos elapsed time = 10.8200 seconds.
Sqrt elapsed time = 3.8600 seconds.
SIQS elapsed time = 880.6199 seconds.
ECM/SIQS ratio was = 0.278866
Total factoring time = 1127.3289 seconds
***factors found***
PRP49 = 5103694751626085298648928673183789087528821155019
PRP34 = 2709140523441953269872116549835923
Hope this helps |
|
Back to top |
|
|
Graphmastur
Advanced Member
Joined: 25 Mar 2009 Posts: 360
|
Posted: 31 Oct 2009 09:27:36 pm Post subject: |
|
|
this is purely for fun. Thank you!! I have an idea for a new algorithm... I will post later. |
|
Back to top |
|
|
|