0

I have some simple operations (subtraction, multiplication) with big numbers (integers). They are so big, that I have to store them into long double variable. That is fine, but for some cases multiplication looses precision.

Example:

A = 84478098072866400.00
B = 419247971803584000000.00

A * B = 35417271278873496315650351919301394432.00

It is obvious, that this is wrong. Result of multiplication should end with sequence of zeros.

I need to keep precision, especially this one (when numbers ends with zeros) because this is the most common case.

My question is, how to do that, please? Is there any way how to force long double to behave better? Or is there any option how to get precision of stored number?

Thanks a lot!

EDIT:

I cannot use any external library. I am trying to solve one problem of ACM competition archive. This is part of it.

I would be fine with precision lost, but I have to detect it. When the numbers are bigger than long double that it is highly probable (maybe certain), that it ends with long sequence of zeros.

Gaim
  • 6,734
  • 4
  • 38
  • 58
  • 2
    If you want to do operations on integers, use integers, not floating point. – Carl Norum Mar 17 '12 at 22:31
  • 1
    @Carl well there is not any variable for numbers with 50 digits and more. Or is it? – Gaim Mar 17 '12 at 22:33
  • No - but that doesn't mean you should be trying to use a built-in type at all. Google 'arbitrary precision'. [GMP](http://gmplib.org/) is a good choice. – Carl Norum Mar 17 '12 at 22:34
  • The mathematical result of that multiplication is `35417271278873496315860673177600000000`, which requires at least 125 bits (126 if it's signed). Few if any compilers directly support integers bigger than 64 bits. To deal with numbers that big without losing precision, you need GMP or something similar. – Keith Thompson Mar 17 '12 at 22:35
  • @KeithThompson: GHC says "I do, I do". But it does use GMP underneath, so I guess you're sorta right. – gspr Mar 17 '12 at 22:39
  • @gspr: I meant C++ compilers. It would be difficult for a C++ compiler to provide arbitrary-precision types *as integer types*. – Keith Thompson Mar 17 '12 at 22:45
  • I agree with you, I was mostly kidding :) – gspr Mar 17 '12 at 22:52
  • If you want useful help, you'll have to tell us the problem you're trying to solve. – TonyK Mar 17 '12 at 23:58

3 Answers3

1

If you're really working with huge integers, you'll want to do arbitrary precision arithmetic where only memory limits the size of your numbers (and no precision is lost). The GNU Multiple Precision Arithmetic Library is a popular library for this (and arbitrary precision arithmetic on rationals and floating point numbers as well), though I'm sure there are others.

gspr
  • 11,144
  • 3
  • 41
  • 74
  • 1
    GMP also supports arbitrary-precision rational and floating-point numbers. – Keith Thompson Mar 17 '12 at 22:33
  • Thanks for answer, I should probably mention that I cannot use any external library. (I am trying to solve one problem in ACM competition archive) – Gaim Mar 17 '12 at 22:36
  • @Gaim: Aha -- well then you'll have to roll your own... or perhaps more likely, attack the problem in a way that doesn't involve computing that huge product :) – gspr Mar 17 '12 at 22:41
  • @gspr Well this product is the answer :( My algorithm is fine, my only problem is a precision. – Gaim Mar 17 '12 at 22:45
0

if you are working with big integers, why not try to write a bigint class instead of using long double? check this:

sample c++ code of a big int class

How to implement big int in C++

Community
  • 1
  • 1
rene
  • 156
  • 1
  • 2
  • 11
0

Do you know how long, in bits, the largest value you need to handle is?

I ask because I noticed that gcc, on some platforms, supports 128 bit integers:
http://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html

so you might be very lucky, if you can get at a platform which supports 128 bit long long, and an up-to-date gcc.

gbulmer
  • 4,210
  • 18
  • 20