Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Steve's Programming Challenge: Weights and Measures
#1
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.  Wink
Reply
#2
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  Big Grin
Fake News + Phony Politicians = Real Problems

Reply
#3
(08-15-2024, 11:49 PM)Pete Wrote: 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  Big Grin

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.  Wink
Reply
#4
(08-15-2024, 11:49 PM)Pete Wrote: 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  Big Grin

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.

Tongue
Reply
#5
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 Big Grin
Fake News + Phony Politicians = Real Problems

Reply
#6
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
Reply
#7
(08-16-2024, 12:24 AM)dano Wrote: 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. Wink

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.
Reply
#8
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
Fake News + Phony Politicians = Real Problems

Reply
#9
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
Reply
#10
(08-16-2024, 12:52 AM)Jack Wrote: 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.  Smile
Reply




Users browsing this thread: 6 Guest(s)