Steve's Programming Challenge: Weights and Measures

[SMcNeill]

So here's a challenge which I'd like to propose for all of our coders here to undertake -- particularly @TerryRitchie @bplus @Pete @Dav , but which I'd truly LOVE to see everyone tackle.

The program concept is very simple -- Write a program that simulates you being a merchant in ancient times.  You have a whole bunch of lead weights, which you can use to measure out how much a customer's gold nugget weighs.

Your available weights are all in the power of two -- you have:

1 four-pound weight.
1 two-pound weight.
1 one-pound weight.
1 half-pound weight.
1 quarter-pound weight.
1 1/8-pound weight.
And so on to give you one of each weight from 4 pounds to 1/256 pounds.

Now the task is to figure out what weights are required to properly and perfectly weigh the following:

A 3 pound gold nugget
A 3/8 pound gold nugget
A 11/32 pound gold nugget
A 1/10 pound gold nugget

Now the first solution is obviously 1 2-pound weight + 1 1-pound weight. 
The question is -- can you find the proper combination for the other three nuggets I've mentioned??

---

Complete this task, and I doubt you guys will ever have any question ever again in the future about how floating point numbers work.  As you're some of our most prolific posters (and teachers) here, I would hope a simple task like this would be enough to help you guys understand the underlying issue with floating point numbers, so when people ask in the future, you'll be able to explain it to them better. 

[Pete]

My father owned an Italian Deli when I was a kid. This reminds me of the time I was taking my first algebra class in junior high school, and I asked him...

Ham is $1.50 a pound, Cheese is $1.00 a pound, and roast beef is $2.50 a pound. If a man walks into your store and has $20 to spend and he wants twice as much roast beef as ham but half as much cheese as roast beef and wants to know how much roast beef, ham, and cheese he will get for $20, what do you tell him?

My Dad's reply was: "I'd tell him to get the hell out of my store!"

Pete 

[SMcNeill]

My father owned an Italian Deli when I was a kid. This reminds me of the time I was taking my first algebra class in junior high school, and I asked him...

Ham is $1.50 a pound, Cheese is $1.00 a pound, and roast beef is $2.50 a pound. If a man walks into your store and has $20 to spend and he wants twice as much roast beef as ham but half as much cheese as roast beef and wants to know how much roast beef, ham, and cheese he will get for $20, what do you tell him?

My Dad's reply was: "I'd tell him to get the hell out of my store!"

Pete 

The trick here is to show the impossibility of the answer.

All weights can be described in relation to the smallest one:

1/256 weight = 1 of the smallest   (1/256)
1/128 weight = 2 of the smallest   (2/256)
1/64   weight = 4 of the smallest   (4/256)

..see where I'm going with this here?

Now, 11/32 can also be represented in relation to that smallest size.  11/32 = 88/256.    As 88 is a whole number, we can pick out whole number combinations to match that.   a 1/4 weight  (8/32) + a 1/16 weight (2/32) + a 1/32 weight = 11/32...     Perfect match.

The problem comes when you get to the 1/10 pound nugget.   That's 25.6/256...   Our values only represent WHOLE numbers.  We might move the scales to 25/256, or over to 26/256, but it's *IMPOSSIBLE* to get 25.6/256 pounds.   

It's the inherent limit of binary math and floating point numbers.  It's literally IMPOSSIBLE to perfectly represent some values.  You can divide your weights in half until they're on the atomic level, and... you're still not going to get 1/10 represented perfectly.  

An exercise like this is the perfect way for folks to visualize what's going on under the hood with floating point values. 

[SMcNeill]

My father owned an Italian Deli when I was a kid. This reminds me of the time I was taking my first algebra class in junior high school, and I asked him...

Ham is $1.50 a pound, Cheese is $1.00 a pound, and roast beef is $2.50 a pound. If a man walks into your store and has $20 to spend and he wants twice as much roast beef as ham but half as much cheese as roast beef and wants to know how much roast beef, ham, and cheese he will get for $20, what do you tell him?

My Dad's reply was: "I'd tell him to get the hell out of my store!"

Pete 

Your story of your dad also reminds me of one my own father used to tell years ago.

One of the nearby neighbors had 3 sons and 17 horses.  When he passed away, the will read:  "I want to give my oldest son 1/2 of my horses, my middle son 1/3 of my horses and my youngest son 1/9 of my horses."   

The family had no idea how to handle such a situation, so they asked my grandfather for help.   He thought on the issue that night, went to bed, and rode over the next morning on his old horse and gave it to the family as a funeral present.

Now, it wasn't so hard to sort out what to do:
The oldest got 1/2 of 18, which was 9 horses.
The middle child got 1/3 of 18, which was 6 horses.
The youngest child got 1/9 of 18, which was 2 horses.

And the horse left over, my grandfather claimed for himself, as fee for solving their problem, as he rode back home later that morning on the same horse which he rode in on.

[Pete]

I tried that puzzle using donkeys but the best I could come up with was a 1/2 ass solution.

Okay, I'll tackle the middle 2....

1/4 + 1/8 = 3/8
1/4 + 1/16 + 1/32 = 11/32

Pete

[dano]

I wrote my program to check all combinations of the above and discovered that the .1 LB could get close, but not exact:

Code: (Select All)

'1 four-pound weight.

'1 two-pound weight.

'1 one-pound weight.

'1 half-pound weight.

'1 quarter-pound weight.

'1 1/8-pound weight.

'And so on to give you one of each weight from 4 pounds to 1/256 pounds.

'

'Now the task is to figure out what weights are required to properly and perfectly weigh the following:

'

'A 3 pound gold nugget

'A 3/8 pound gold nugget

'A 11/32 pound gold nugget

'A 1/10 pound gold nugget



Dim mask$(2500)

Dim w##(20)



'w = weights

w##(1) = 4

w##(2) = 2

w##(3) = 1

w##(4) = .5

w##(5) = .25

w##(6) = .125

w##(7) = .0625

w##(8) = .03125

w##(9) = .015625

w##(10) = .0078125

w##(11) = .00390625





'si = sale items

si##(1) = 3

si##(2) = .375

si##(3) = 11 / 32

si##(4) = .1



'load binary masks

For x = 1 To 2047

    mask$(x) = Right$("000000" + Decimal2Binary$(x), 11)

Next x





For itemTOsell% = 1 To 4

    For combinationOfWeights% = 1 To 2047

        totalWeight## = 0

        For bit = 1 To 11

            If Mid$(mask$(combinationOfWeights%), bit, 1) = "1" Then

                totalWeight## = totalWeight## + w##(bit)

            End If

        Next bit

        If totalWeight## = si##(itemTOsell%) Then

            Cls

            Print "MATCH##"

            Print "          itemTOsell%="; itemTOsell%

            Print " Total of weights used="; totalWeight##

            Print "    si##(itemTOsell%)="; si##(itemTOsell%)

            Print "Weights to use:"

            For z = 1 To 11

                If Mid$(mask$(combinationOfWeights%), z, 1) = "1" Then

                    Print w##(z)

                End If

            Next z

            i$ = "": While i$ = "": i$ = InKey$: Wend

        End If

    Next combinationOfWeights%

Next itemTOsell%





Function Decimal2Binary$ (number&)

    If number& = 0 Then Exit Function

    Do

        remain% = Abs(number& Mod 2) ' remainder is used to create binary number

        number& = number& \ 2 ' move up one exponent of 2 with integer division

        BinStr$ = LTrim$(Str$(remain%)) ' make remainder a string number

        Binary$ = BinStr$ + Binary$ ' add remainder to binary number

    Loop Until number& = 0

    Decimal2Binary$ = Binary$ 'binary result

End Function

[SMcNeill]

I wrote my program to check all combinations of the above and discovered that the .1 LB could get close, but not exact:

Exactly. And that's the error which we see in floating point math. We can get close to representing some values, but never exact.

That *close but not exact* is the cause of floating point errors that we see when doing math. It's simply impossible to perfectly represent some values in binary-numbers, just as it's impossible to perfectly represent some numbers in standard base-10 values.

What is 1/3 as a decimal?

0.33333333333333333333333333333333333333333333333333333333333(keep holding down that 3 key... you haven't got it perfect yet...)

We can't perfectly represent 1/3 in decimal.

We also can't perfectly represent 1/10 in binary. We get "close, but not exact", and that "close" is where our math errors and rounding errors occur over time in our programs.

[Pete]

When I was working out calculations in string math, I simply kept my calculator tracking in fractions, instead of decimals. That allowed for reverse calculations to get back to 1, instead of .9999999999999999999 and so on.

Pete

[Jack]

Steve, I agree with you but most of the time floating-point math works surprisingly well, but then you have cases where it fails catastrophically

[SMcNeill]

Steve, I agree with you but most of the time floating-point math works surprisingly well, but then you have cases where it fails catastrophically

Aye.  Folks just need to realize *WHY* it tends to fail, when it does.

FOR i = 1 TO 100 STEP 0.1
   PRINT i
NEXT

^That's *going* to have issues in it, just for the simple fact that we're adding 0.1 -- a number we can't represent perfectly -- over and over in that loop, which compounds the level of error until it's quite noticeable.  It's not a flaw in QB64.  It's not a glitch in the matrix.  There's no "Fix" for it.   That's just life with floating point values.  They're fast -- but they're imprecise.

If one needs precision, use integer values (Loop from 10 to 1000 and divide by 10).  It's why banks track money by pennies and not dollars.  You have 12345 pennies in the bank, not $123.45 dollars.   The dollars is just formatted at the PRINT end, to make it easier for people to understand and relate to.  Internally, it's all pennies.