OJ Board

i guess u've to write it ur self
atleast thats the best way!

fellow sufferer,
can help
if u mail me.
best of luck.
suman

i guess u've to write it ur self
atleast thats the best way!

fellow sufferer,
can help
if u mail me.
best of luck.
suman

You know how to add, subtract, etc with pen and paper? Simulate that in your program...

Yes, that' the possible way for solve.
Simulate your imagination............

For addition of long-digits numbers like you mentioned, we might have to upgrade our current "base-10" perspective to some higher base ... like "base-10^n" where n > 1, ... just be careful on overflows if we use bigger base. That would already be an improvement ...

-turuthok-

Addition and subtraction are quite easy, but what about multiplication, and, even worse, division. I have an algorithm for division that guarantees TLE for almost all problems , but I cannot see where I can improve it. There must be some standart fast methods for that. Overflows are even worse in this type of problems and I reduced the efficiency of the algorithm drastically to ensure I am avoiding these cases. I do not know if that may be the problem with my code.

Any suggestions?

vega.marcin wrote:I know how to add or substract on paper but when I've had to solve a problem where it was said that I have to add two one-milion-digit numbers I used method of addition (as I do it on paper) and it was to slow (I've got TLE). What should I do? I dont know what to do, however I have tried to write it myself.

it shouldnt time out, however bad it maybe. As long as your algoirthm is O(n) (just add straight down )

Addition and subtraction are quite easy, but what about multiplication, and, even worse, division. I have an algorithm for division that guarantees TLE for almost all problems , but I cannot see where I can improve it. There must be some standart fast methods for that. Overflows are even worse in this type of problems and I reduced the efficiency of the algorithm drastically to ensure I am avoiding these cases. I do not know if that may be the problem with my code.

arrgh i have the exactly same problem!! the routines I wrote is much slower than other people's! everytime i solve a bigint problem, I am never faster than other people in the ranking list! in fact, in a problem that i take 3 seconds, most others only take 1/10 of a second!! that really gets me. I am still getting TLE on 10083 Division. I know that i have optimized every other aspects of my code (including determining exactly when to display the number through O(1)) Therefore either i am missing something (typo/infinite loop) or my only problem would naturally be too slow of an algorithm on the BigInt part!

Can anyone share the algorithms behind the division? that would be very useful. i have found a few pieces of code on the net, but i dont quiet understand what they did.

If you have JDK installed on your box, I suggest opening up the file BigNumbers.java locted in (usually) the Classes.zip file.

This file is huge, and contains methods for +, -, *, /, pow, sqrt, log, and some others.

From what I can tell, this class is as optimized as you can get for arbitrary precision. It may take you a little while, but you can cut and paste and modify the parts you need. As long as you stick to the logical flow, I believe it can be ported to any language.

Just be careful of the constants (such as LONG_MASK) which needs to be changed for whatever architecture you are using.

I am a java programmer here and GCJ does not support BigNumbers, so I cut out the parts I needed and stuck them in my program.... It works!

good idea, thanks a million!

Or for C code you can try this link: http://www.cs.sunysb.edu/~skiena/392/programs (code from Programming Challenges book - though their C programming style is a bit wacky to say at least...)