programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Paul Clapham
• Bear Bibeault
• Jeanne Boyarsky
Sheriffs:
• Ron McLeod
• Tim Cooke
• Devaka Cooray
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Jj Roberts
• Stephan van Hulst
• Carey Brown
Bartenders:
• salvin francis
• Scott Selikoff
• fred rosenberger

# how to recognize 2 ^(-100_000)

Bartender
Posts: 4103
156
hi all,

was doing a HackerRank exercise the other day. A series was given, with the question what was the smallest integer equal to or greater than the outcome.
The theoretical outcome of one of the series was 99_999 + 2 ^(-100_000), so the correct answer was 100_000. However, I got 99_999 using doubles. I tried using BigDecimals, but that was very way too slow. Any suggestions?

Saloon Keeper
Posts: 12428
269
Hard to make suggestions without knowing the problem or how you calculated the answer.

Piet Souris
Bartender
Posts: 4103
156
Well, in short it goes:
given an array a with all elements between 1 and 100_000. The Nth term of a sequence is a[0] / 2 + a[1] / 4 + a[2] / 8 + ... + a[N - 1] / (2 ^ N). (0 <= N <= a.length)
The question is: what is the smallest integer equal to or greater than the final term?

I used the simple:

(in fact I used this for loop:

Stephan van Hulst
Saloon Keeper
Posts: 12428
269
Yeah. The problem is that by applying the division operator n times, you're also adding up the rounding error n times.

What you want to do instead is create a Fraction class that keeps the numerator and denominator as separate integer fields. You would then only divide both of them to simplify the fraction. For each fraction in the sum series, add the fraction to your existing fraction to get the next term. As ugly as it is, you may want to make your Fraction class mutable and have an add(int otherNumerator, int otherDenominator) method mutate the current fraction instead of returning a new one. This will save you the overhead of object instantiation, which is likely a big factor when using BigDecimal.

Add a ceiling() method that performs the final integer division of the numerator by the denominator and adds 1 if the fraction is positive and the denominator is not a divisor of the numerator.

Stephan van Hulst
Saloon Keeper
Posts: 12428
269
To further improve performance, you only have to simplify the fraction when the numerator or denominator no longer fit in an int. Example:

Piet Souris
Bartender
Posts: 4103
156
Thanks, Stephan, certainly a method to remember. But I did it in a couple of minutes, and that was about the time I wanted to spend on this exercise. I saw some solutions (python and c++) of course that did it in a loop and apparently got it right. I come back to this when I have time to look at it again. Thanks again!

Stephan van Hulst
Saloon Keeper
Posts: 12428
269
Given your code above, using my Fraction example it would look like this:

Piet Souris
Bartender
Posts: 4103
156
morning Stephan,

just had a closer look at your Fraction class, and it looks concise. I considered (for a moment) a similar approach, since I realised that a double would certainly suffer from rounding errors. But since from term 100 the denominator would be 2 ^ 100, I presumed these errors would be irrelevant. And secondly, the denominator would grow to an incredible 2 ^ 100_000 (not taking simplification into account) fearing that would not even fit into a BigInteger (could be wrong though). My last thought was to multiply the nominators with 2 ^ 100000, to get rid of the denominators, same problem of course. And in my solution, I limited the outcome to the first 1_000 entries. I passed 15 of the 16 tests, and I was satisfied.

But I give your code a try, curious whether it works or not.

Again, thanks, and a cow for your efforts!

Stephan van Hulst
Saloon Keeper
Posts: 12428
269
Thanks a lot Piet! Let me know whether it works or not. I haven't tested it, but I did something similar when I had to use this in a real-life scenario: In the student apartment where I used to live, we had a website that would keep track in a calendar which one of us would cook on what day and it would also keep a list of expenses and who had to pay for what.

It turned out that when we summed the credit/debet amount of all residents, it would never arrive at zero, but a couple of euros magically appeared or disappeared. This was because to calculate the credit/debet of each resident, it divided the price of each item by the number of residents that had to pay for it, and then summed the fractions together. The rounding errors, in fractions of cents, were enough to make up several euros.

When I rewrote the website, I calculated the numerator and denominator separately, and the rounding error was limited to half a cent per resident.

Piet Souris
Bartender
Posts: 4103
156
When doing an actuarial P&L, we always had to make use of the post: "difference with accountancy". That simply meant there were some results we couldnt explain, and if that post was not too big, the accountant didn't mind. A lot easier than writing a new website

I gave the Fraction class a try, adapting the class to the specifics of the assignment. Since the denominator is always of the form: 2^x, I only store x. I simplify where possible, and I hoped that that would be sufficient to keep the nominator as low as possible. Well, that did not work, for instance: if the series is 1/2 + 1/4 + 1/8 + .... then no term can be simplified. and so the numerator overflows after term 63 (if not earlier). So, the long nominator must be replaced by a BigInteger. I'll leave that to the real enthousiast (if any).
Here's the code:

Piet Souris
Bartender
Posts: 4103
156
Final word:

I made the numerator a BigInteger, and I managed to get a ceiling value of 100.000.
However, the code is slow and will lead to a timeout error.

So, typically a case of: surgery succes, patient dead.

Marshal
Posts: 70651
288

Piet Souris wrote:. . . surgery succes, patient dead.

Hahahahahahahahaha!

If there any way you can evaluate the second term as 0.0 < x < 1.0 so you know you are rounding up?

Piet Souris
Bartender
Posts: 4103
156
Not that I know of. The value that exceeds 99.999 is 2 ^(-100.000) and so, if you use a double, it will be 0.0. Try

The way I got my ceiling correct is that both numerator and (2 ^denominator) are precise BigIntegers, and I calculate the ceiling as:

Master Rancher
Posts: 3696
44
Piet, can you give a link to the full original problem statement?  I'm curious how this was being used.  Thanks!

Piet Souris
Bartender
Posts: 4103
156
hi Mike,

Chief Hopper

Mike Simmons
Master Rancher
Posts: 3696
44
Thanks, Piet.  Fun problem.  I was thrown by your emphasis on specifically evaluating the final term - isn't it really necessary to check the sum of all the terms?  Which I think is what you end up doing, though I'm not entirely sure how all the code got combined in the end.

Here's what I came up with, which passes all their tests without timeout:

I imagine it could be faster with a mutable version of BigInteger.  Also it should be possible to put an upper bound on the size of the remaining terms in the series, and stop adding terms once the maximum possible value of the remaining terms falls below the amount that might increase the result by 1 or more.  But this seems to work well enough for now.

Mike Simmons
Master Rancher
Posts: 3696
44
Or (streamier version for fun):

Piet Souris
Bartender
Posts: 4103
156
hi Mike,

brilliant!

I did not know of the existance of these shift-operators, but they really are extremely handy here. I guess that 'shiftRight(arr.length)' is very much faster then dividing by 'TWO.pow((100_100)'.

The reason I concentrate on what you call the 'last term' is that if you start with an energy of X, then after the first climb, you have the requirement that X >= a[1] / 2 (indexing from 1), and after the next step you also get that X >= a[1] / 2 + a[2] / 4, et cetera. Since all the a[i] are >= 1, the right-hand sums form a monotone increasing sequence. So if X >= the last term, then it is also >= all other terms.

Thanks, learned something new here.

 Hey, I'm supposed to be the guide! Wait up! No fair! You have the tiny ad! Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton