I’ve got a set of scales, but no weights; I’m making some to weigh from 1mg up to 100g in 1mg steps. I’d like to minimise the number of weights needed. Using a binary sequence (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536mg) gives 17 individual weights and allows unknown masses up to 131.071g. The most efficient algorithm I can come up with gives the correct mass in no more than 17 weighings: with the unknown mass in pan 1, (a) add the heaviest known weight (65526mg) to pan 2; (b) if pan 1 is heavier, add the next lighter weight to pan 2, then go back to (b), otherwise remove the last kmown weight added and add the next lighter mass to pan 1 and go back to (b); repeat until the scales balance. This is basically a maximally efficient successive approximation technique.

I’ve tried using a binary-tree-type search for this (start with the middle weight in pan 2, then pick the mid-point of the heavier or lighter weights depending on whether that’s lighter or heavier than what’s in pan1, etc); that doesn’t work because the unknown mass is the sum of several known weights rather than a single weight (usually). It’s also complicated by the fact that the sequence of masses is exponential rather than linear.

A method alternative to the binary sequence is balanced ternary, where the known masses are powers of 3 (1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147mg) for a total of 12 masses, allowing up to 265.720g (note that not including the 177147mg mass only allows measuring up to 88.573g.) Then the different masses can be found as follows (the unknown mass is in pan 1):

Total	Pan 1 (with unknown)	Pan 2
1mg	0mg	1mg
2mg	1mg	3mg
3mg	0mg	3mg
4mg	0mg	3mg+1mg
5mg	3mg+1mg	9mg
6mg	3mg	9mg

etc

I’m trying to find an efficient algorithm for finding any unknown mass (in pan 1) to minimise the total number of weighings (using either binary or balanced ternary, but probably the latter,) but not having as much success as I’d like. I’m multiplying the known weights in pan 1 by -1 for the mathematics, which works, but it’s not really helping.

Has anyone here got any suggestions?

btm said:

I’ve got a set of scales, but no weights; I’m making some to weigh from 1mg up to 100g in 1mg steps. I’d like to minimise the number of weights needed. Using a binary sequence (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536mg) gives 17 individual weights and allows unknown masses up to 131.071g. The most efficient algorithm I can come up with gives the correct mass in no more than 17 weighings: with the unknown mass in pan 1, (a) add the heaviest known weight (65526mg) to pan 2; (b) if pan 1 is heavier, add the next lighter weight to pan 2, then go back to (b), otherwise remove the last kmown weight added and add the next lighter mass to pan 1 and go back to (b); repeat until the scales balance. This is basically a maximally efficient successive approximation technique.

I’ve tried using a binary-tree-type search for this (start with the middle weight in pan 2, then pick the mid-point of the heavier or lighter weights depending on whether that’s lighter or heavier than what’s in pan1, etc); that doesn’t work because the unknown mass is the sum of several known weights rather than a single weight (usually). It’s also complicated by the fact that the sequence of masses is exponential rather than linear.

A method alternative to the binary sequence is balanced ternary, where the known masses are powers of 3 (1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147mg) for a total of 12 masses, allowing up to 265.720g (note that not including the 177147mg mass only allows measuring up to 88.573g.) Then the different masses can be found as follows (the unknown mass is in pan 1):

Total	Pan 1 (with unknown)	Pan 2
1mg	0mg	1mg
2mg	1mg	3mg
3mg	0mg	3mg
4mg	0mg	3mg+1mg
5mg	3mg+1mg	9mg
6mg	3mg	9mg

etc

I’m trying to find an efficient algorithm for finding any unknown mass (in pan 1) to minimise the total number of weighings (using either binary or balanced ternary, but probably the latter,) but not having as much success as I’d like. I’m multiplying the known weights in pan 1 by -1 for the mathematics, which works, but it’s not really helping.

Has anyone here got any suggestions?

I have a suggestion, but it’s a bit lateral.

I made a set of accurate scales some decades ago, for a total cost of a few cents, to weigh hailstones. As hailstones vary in weight from about 5 mg to 0.5 kg I had to get creative. This is about the same range of weight that you have.

The method I used was to make a right angle of some lightweight material, in my case stiff cardboard, and support it from above through a hole in the angle. Attached to one leg of the card is a protractor. Attached to the pivot point is a plumb bob. From the ends of the legs I suspended two small plastic bags, one to contain the hailstone and the other to contain the fixed weight.

The tangent of the angle that the plumb bob makes on the protractor gives the ratio of the fixed weight to the weight of the hailstone. ie. you don’t have to get a weight to match your hailstone, a weight within a factor of 5 will suffice.

With this method and a set of just four weights between 25 mg and 100 g (with a bit of calibration needed for the smallest weight because of the weight of the protractor) I was able to measure the whole range from 5 mg to 0.5 kg to about 2% accuracy.

I know that this is not what you were asking. But as an engineer, it’s the % accuracy that matters, not the error in mg.

See my post above for a making a blance scale that bypasses the problem.

Balanced ternary will work.

Algorithm A

Call your unknown weight ‘Y’.
Let ‘I’ be your weight number, starting downward from the heaviest being I=1, call this weight W_1.

Start with weight 1. Is X heavier or lighter?
If heavier add weight 2. If lighter, subtract weight 2 (ie. put on same side as unknown).
Is X closer to W_1 or weight W_1 +- W_2?
If W_1 is closer then discard W_2 and continue with W_3
If W_1 +- W_2 then retain W_2 and continue with W_3
etc through all of the weights.

Now, the open question in the above is the word “closer”. On a computer, “closer” is easy because you just subtract one number from another. In real life with 3 or fewer weights, “closer” is also easy be judging the speed at which pans ris and fall.

Beyond 3 weights in real life, judging the relative speed at which pans rise and fall can be tricky. I’d keep track of all situations where “closer” is not obvious, and try both tracks one at a time.

Algorithm B

Now let’s suppose that “closer” is unattainable, and that all you can do is use greater than, less than and equal to.

Call your unknown weight ‘Y’.

In that case the algorithm you want is a binary search. You bracket the solution between a set of weights that is known to be heavier and one that is known to be lighter. Let the lighter combination of weights sum to X0 and the heavier set of weights sum to X1. Then try a set of weights that adds to X = (X0+X1)/2. If X < Y then set X0 = X. If X > Y then set X1 = X.

Repeat.

Algorithm C

Use a table to evaluate a ternary number

Your ternary number is 0,+,-, rather than 0,1,2.
Say you have N weights, then your ternary number (in Fortran) would be

integer weights(N,-1:1)

Then calculate your weight from the ternary number, either using a ternary tree or just run through the possibilities one at a time.

Once calculated as a table, you can directly invert to get the combination of physical weights required to make up any given total weight. eg.
1000 mg = ++0+00+ = 729+243+27+1
500 mg = +-0+—- = 729-243+27-9-3-1

Is that what you’re looking for, or something else?