Big numbers; Maybe easy, but not for me.

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

bignum

Post by sumankar »

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

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

bignum

Post by sumankar »

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

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

Post by junjieliang »

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

Arnold
New poster
Posts: 10
Joined: Sun Aug 03, 2003 2:46 pm

Post by Arnold »

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

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

mafattah
New poster
Posts: 23
Joined: Fri Apr 26, 2002 1:00 am
Location: Cairo, Egypt

What about multiplication and division

Post by mafattah »

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 :lol: , 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?

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

Post by bugzpodder »

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

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx »

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!

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

Post by bugzpodder »

good idea, thanks a million!

Viktoras Jucikas
New poster
Posts: 22
Joined: Sun Oct 20, 2002 6:41 pm
Location: Lithuania
Contact:

Post by Viktoras Jucikas »

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

Post Reply

Return to “Algorithms”