I have a number of very large length may be upto 50 digits. I am taking that as string input. However, I need to perform operations on it. So, I need to convert them to a proper base, lets say, 256.
What will be the best algorithm to do so?
Asked
Active
Viewed 2,879 times
2
-
1What's wrong with converting it to base 2, then using the processor to perform your arithmetic? – Marcin Jan 06 '12 at 13:17
-
In any case, there is a generic base-conversion algorithm. Try googling it. – Marcin Jan 06 '12 at 13:18
-
Increasing the base will reduce the number of operations , that i will require for my addition – Prashant Singh Jan 06 '12 at 13:20
-
@Marcin Anyways, how can u add two 50 digits number ?? – Prashant Singh Jan 06 '12 at 13:31
-
The processor anyway works with binary number. Adding a number represented either in base 2 or base 256 (or whatever you want) will not change anything to the fact that your numbers are greaters than the biggest number allowed by your computer. So see Basile's answer. – Manuel Selva Jan 06 '12 at 13:38
-
@ManuelSelva It will be too small if represented in 2^15 as base. – Prashant Singh Jan 06 '12 at 13:40
-
I didn't get your problem ... – Manuel Selva Jan 06 '12 at 13:42
-
2^15 is approximately 30000, now once i convert my number into vectors of this range, i can do the operations easily on these individual values – Prashant Singh Jan 06 '12 at 13:47
-
You can do them easily in any power of two base from 2^1 though 2^64. And they're all equivalent anyway, they're just different groupings of the same bits. – harold Jan 06 '12 at 14:56
-
@Manuel: That's not entirely true. For example doing large decimal arithmetic you could work in base 10 or base 1000000000 (each "digit" fits in a 32-bit int). The latter will generally be a LOT faster. – R.. GitHub STOP HELPING ICE Jan 06 '12 at 17:54
-
@R.. I didn't get your comment. Can you explain me a little bit more ? – Manuel Selva Jan 06 '12 at 17:59
-
@Prashant, so you are not only converting your number in an other base but also splitting it into several numbers ? – Manuel Selva Jan 06 '12 at 18:01
-
@ManuelSelva yup, i am storing them separately in an array – Prashant Singh Jan 07 '12 at 02:54
-
Finally, I am done with making all calculations. Can anyone suggest me how to print such a large value ? – Prashant Singh Jan 08 '12 at 11:45
1 Answers
10
Multiple-precision arithmetic (a.k.a. bignums) is a difficult subject, and the good algorithms are non intuitive (there are books about that).
There exist several libraries handling bignums, like e.g. the GMP library (and there are other ones). And most of them take profit from some hardware instructions (e.g. add with carry) with carefully tuned small chunks of assembler code. So they perform better than what you would be able to code in a couple of months.
I strongly recommend using existing bignum libraries. Writing your own would take you years of work, if you want it to be competitive.
See also answers to this question.
Community
- 1
- 1
Basile Starynkevitch
- 223,805
- 18
- 296
- 547
-
Can you recommend a *good* bignum library? GMP is definitely not one; it unconditionally aborts the calling program on memory exhaustion which is easy to trigger with external inputs unless you add extensive checking... – R.. GitHub STOP HELPING ICE Jan 06 '12 at 17:56
-
For me, GMP is good enough. But I am not a bignum expert, only occasionally use one. You might for instance try to code your application in Common Lisp with SBCL. I believe it has different bignums, and might handle a little better memory exhaustion, which is in my opinion a case for abortion... And wikipedia lists other bignum libraries. – Basile Starynkevitch Jan 06 '12 at 18:16
-
And I don't see the practical issue here. GMP allows you to convert a string to bignums. If you are scared about huge bignums, just restrict the allowable string size. Also, GMP is free and open source software, so feel free to improve it as you like. Don't forget to publish your patches! – Basile Starynkevitch Jan 06 '12 at 18:26
-
As an example, GMP is completely useless (serious vuln) for a general-purpose database server that wants to store and compute with bignums. It can't report errors on resource exhaustion issues; it will just crash. Even if you forbid *input* of insanely large numbers, you'd have to check that things don't blow up in calculations, and that's hard (read: impossible) if you support nontrivial expressions. – R.. GitHub STOP HELPING ICE Jan 07 '12 at 00:11
-
Again, the solution is to improve GMP as you like. It is free software. – Basile Starynkevitch Jan 07 '12 at 07:40
-
I agree this would be a solution, but it would require quite extensive changes that may not be accepted upstream, so it could very well amount to a fork and all the maintenance burden that goes with forking. Thus I don't think the answer is so simple. – R.. GitHub STOP HELPING ICE Jan 07 '12 at 13:24
-
You cannot know if a patch will be accepted before submitting it (and usually, it is not a yes/no question; often the patch is accepted after discussion with the community & improvements). – Basile Starynkevitch Jan 08 '12 at 16:42