Big numbers; Maybe easy, but not for me.
Moderator: Board moderators
bignum
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
atleast thats the best way!
fellow sufferer,
can help
if u mail me.
best of luck.
suman
bignum
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
atleast thats the best way!
fellow sufferer,
can help
if u mail me.
best of luck.
suman

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
For addition of longdigits numbers like you mentioned, we might have to upgrade our current "base10" perspective to some higher base ... like "base10^n" where n > 1, ... just be careful on overflows if we use bigger base. That would already be an improvement ...
turuthok
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
What about multiplication and division
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?
Any suggestions?

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
it shouldnt time out, however bad it maybe. As long as your algoirthm is O(n) (just add straight down )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 onemiliondigit 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.
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!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.
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.

 Experienced poster
 Posts: 114
 Joined: Wed Jul 30, 2003 10:30 pm
 Location: Newfoundland, Canada (St. John's)
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!
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!

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm

 New poster
 Posts: 22
 Joined: Sun Oct 20, 2002 6:41 pm
 Location: Lithuania
 Contact:
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...)