Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (757) Games in Android Showcase (229) games submitted by our members Games in WIP (844) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 256 Math library is done.  (Read 4221 times) 0 Members and 1 Guest are viewing this topic.
Raghar

Junior Devvie

Ue ni taete 'ru hitomi ni kono mi wa dou utsuru

 « Posted 2005-09-27 18:59:43 »

I finally done a library for Java with support of 256 bit integer arigthmetic, and other operations. Actually I did also 128 bit one.  These have support for both signed and unsigned numbers.
So some results

add 101 - 150 ms
sub simillar
div  between 10 s - 19 s
mul 1300 ms

All tested for 1000000 itereations.  Thus for example add is aprox up to 250 cycles.

I know I should post it in anoncements, but I would like to know if I didn't missed any algorithms that could speed things up.
Mark Thornton

Senior Devvie

 « Reply #1 - Posted 2005-09-28 07:52:26 »

Rather hard to know if you have missed any better algorithms without knowing which ones you have actually used. It certainly possible to improve on the classical algorithms for multiplication and division.
Raghar

Junior Devvie

Ue ni taete 'ru hitomi ni kono mi wa dou utsuru

 « Reply #2 - Posted 2005-09-28 14:52:09 »

For multiplication, I used the standard algorithm

q[0] = a[0] * b[0]

q[1] = a[0] * b[1] + a[1] * b[0]

and so on

For example 10 * 22
q[0] = 0 * 2
q[1] = 0 *2 + 1 * 2
...

For division, I used the algorithm with a subtraction and a bitshift.
 Games published by our own members! Check 'em out!
Mark Thornton

Senior Devvie

 « Reply #3 - Posted 2005-09-28 15:18:10 »

Have a look at section 4.3.3 of Knuth's "The Art of Computer Programming" volume 2 (Seminumerical Algorithms).
pepijnve

Junior Devvie

Java games rock!

 « Reply #4 - Posted 2005-09-29 07:58:46 »

I'm probably missing the point, but doesn't BigInteger cover this stuff already?
Mark Thornton

Senior Devvie

 « Reply #5 - Posted 2005-09-29 13:05:24 »

I'm probably missing the point, but doesn't BigInteger cover this stuff already?
The point would be performance. Is it possible to create a class that, for 256 bit values, is significantly faster than BigInteger?
pepijnve

Junior Devvie

Java games rock!

 « Reply #6 - Posted 2005-09-29 13:20:04 »

The point would be performance.
Why didn't I think of that?

Is it possible to create a class that, for 256 bit values, is significantly faster than BigInteger?
That was kind of my next question. How do those performance figures compare to doing the same thing with BigInteger?

Edit:
It might also be intersting to compare against other math libs like apfloat (first one I encountered while googling on BigInteger performance).
Raghar

Junior Devvie

Ue ni taete 'ru hitomi ni kono mi wa dou utsuru

 « Reply #7 - Posted 2005-09-29 22:52:26 »

In comparison to the MutableBigInteger? Dunno multiplication would be same. MutableBigInteger is spawning new array for outcome, while my library doesn't create any new object after inicialization.
I have better subtraction, because MutableBigInteger used too much mathematically rigorous algorithm.

The biggest problem with these libraries is, they can't access carry flag from Java. So they are running sometimes at half speed.
Pages: [1]
 ignore  |  Print

 EgonOlsen (76 views) 2018-06-10 19:43:48 EgonOlsen (56 views) 2018-06-10 19:43:44 EgonOlsen (76 views) 2018-06-10 19:43:20 DesertCoockie (256 views) 2018-05-13 18:23:11 nelsongames (156 views) 2018-04-24 18:15:36 nelsongames (155 views) 2018-04-24 18:14:32 ivj94 (896 views) 2018-03-24 14:47:39 ivj94 (157 views) 2018-03-24 14:46:31 ivj94 (809 views) 2018-03-24 14:43:53 Solater (173 views) 2018-03-17 05:04:08
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org