Java is slow. Can I rewrite it in C?

[Graphmastur]

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...

[darkstone knight]

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...)

[Graphmastur]

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.

[darkstone knight]

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)

[Graphmastur]

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.

[Graphmastur]

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.

[darkstone knight]

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:

[Graphmastur]

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.

[Mapar007]

@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.

[Graphmastur]

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.

[magicdanw]

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...

[GloryMXE7]

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.

[Graphmastur]

[Graphmastur]

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?

[darkstone knight]

seeing as "thread-1" doesnt throw an error, you might be using duplicate labels / vars

[Graphmastur]

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!

[Mapar007]

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)

[Graphmastur]

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]

[Lionel Debroux]

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:

[Graphmastur]

this is purely for fun. Thank you!! I have an idea for a new algorithm... I will post later.