0

I have the following statement. 

d = (pow(a,2*l+1)+1)/(val+1);

Here,

  • val, a and l are variables which are of no relation to the question.
  • the numerator can exceed long long int range.
  • denominator is a divisor of the numerator.

But the final answer d will surely be under the long long int range. How to calculate d without loss of accuracy? I would prefer an answer without converting them to array and using grade school multiplication and division.

Spektre
  • 49,595
  • 11
  • 110
  • 380
Astitwa Saxena
  • 3
  • 5
  • 1
    You should say what language you target. I would guess c or c++. – t.niese Nov 12 '15 at 18:30
  • 2
    `pow` for c and c++ both return floating point numbers [std::pow](http://en.cppreference.com/w/cpp/numeric/math/pow), depending on the input type you will get up to `long double` as output, so exceeding the `long long` should not be a problem, with respect to an _overflow_, but you for sure might or will geht a loose of accuracy, but depending of the use-case this might still be acceptable. If this is not acceptable then you need to use a library like [GNU GMP](https://gmplib.org/). – t.niese Nov 12 '15 at 18:42
  • I cannot afford to be non-accurate. My code gives wrong answer for calculation on large numbers where numerator can reach upto 10^21. Is there a method of not loosing any accuracy? It is given that denominator will always divide the numerator with no remainder left – Astitwa Saxena Nov 12 '15 at 18:46
  • 1
    `[...]My code gives wrong answer for calculation on large numbers[...]` you need to explain why you get or you think you get a wrong result (e.g. doing a `==` test with floating points will never work like expected). Otherwise the only answer is that there is no way around a big number library. – t.niese Nov 12 '15 at 18:47
  • when i calculate what my code is supposed to answer using a calculator, it does not match with the output my code gives me for a particular set of values. although the difference is only of 1 or 2 but not exact, which is enough to give me a wrong answer on my judge – Astitwa Saxena Nov 12 '15 at 18:57
  • i am multiplying the value of d in the desired answer for different set of values val,a and L. It is given that the answer does not exceed long long int range. – Astitwa Saxena Nov 12 '15 at 19:01
  • 1
    How do you know your calculator isn't wrong? When you say your judge, does this mean you're submitting this for a programming competition of some sort? – Teepeemm Nov 13 '15 at 02:42
  • Possible duplicate of [Avoiding overflow in integer multiplication followed by division](http://stackoverflow.com/questions/5542037/avoiding-overflow-in-integer-multiplication-followed-by-division) – Fabio says Reinstate Monica Nov 13 '15 at 09:28

2 Answers2

0

I don't have time to write a proper answer now; I'll expand this later if I get a chance. The basic idea is to use the grade-school algorithm, working with "digits" that are a power of the denominator. Do a Google search for "Schrage multiplication" or look here for references.

user448810
  • 17,381
  • 4
  • 34
  • 59
  • from the title the algorithm you linked is for **modulo arithmetics** instead of for division result or can it be modified? (too lazy to analyze as I approach these tasks differently anyway but you should clarify so it is not confusing others) – Spektre Nov 13 '15 at 09:37
0

I hope the operands are integer too

  1. I would use power by squaring instead of pow

    See Integer power by squaring

  2. while iterating #1

    Each time booth sub-result and denominator are divisible by 2 divide both of them to keep the pow result small and not losing precision or the correctness of result. So each time the LSB bit of both subresult and Denominator is zero shift right both by 1 bit.

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380