Reply to: Maths problem

[EternalOptimist]

oi oi ...EO....comeeeeeeon old chap...tell me that scribbled bit of barely pseudo code is eeeeeeeeeexactly what you're looking for
Tell me what language you're using and I might even see if I can smarten it up appropriately.

It's VBA


I got round it by looping through the values and jiggling with the number type.
not quite as good as a dither, but it works
users say they will accept diferent numbers for the same % , so long as the bottom line is correct


public dblRoundmeUpAS double
public lngLastRoundmeUp as long

function RoundmeUp(myVal)


dblRoundmeUp = dblRoundmeUp + myVal
RoundmeUp = CLng(dblRoundmeUp) - lngLastRoundmeUp
lngLastRoundmeUp = dblRoundmeUp

end

I'm sh1t as maths me

[Olly]

oi oi ...EO....comeeeeeeon old chap...tell me that scribbled bit of barely pseudo code is eeeeeeeeeexactly what you're looking for
Tell me what language you're using and I might even see if I can smarten it up appropriately.

[Doggy Styles]

(although if you know all the distinct percentages but not the number of repetitions of each, then it's a variant of the Frobenius Coin Problem)

Does that apply to the unobtainable score of 19 in a cribbage hand, and whatever it is in rugby union?

[OwlHoot]

the number of variables is an unknown
the % will be 2 dp
n will be an integer

Unknown? I thought you started with a given list of percentages (integers or otherwise) which in effect you had to scale up and round such their sum is some given integer and they deviate minimally as percentages of this sum from the originals.

That's the problem whose solution I sketched. But if you don't even know what the percentages are to start with it's an ill-posed problem.

(although if you know all the distinct percentages but not the number of repetitions of each, then it's a variant of the Frobenius Coin Problem)

[doodab]

veeeeeeeeeery quick answer cos hungry and glanced at thread
add all the rounded numbers up
=999

now you've got to loose 1 somewhere so choose the number with the fractional part closest to .5 and > 0.5 and zap it's fractional part

no repeat the adds of the rounded numbers and u get 998.

P.S. There might (probably) is a fairer way to "allocate" the zapping of the extra 1 but what I just scribbled might be a good way

Whichever rounding scheme you choose you will introduce a rounding error. Either the totals will not add up in some cases or you have to accept different numerical values for identical percentages in other cases. The best way to distribute the error is probably to "dither" the untruncated numerical values before rounding although I suspect this won't actually achieve what you want.

[Olly]

ok part way through shepherds' pie so can spare a few more ticks but I'm not going to check this mmmmmmmmkay

array_percentages (0.2,0.1,0.7)
array_numbers ()
target = 998
tobezapped
bestsofar = 0

for n = 1 to max_elements(array_percentages)
array_numbers(n) = array_percentages(n) * target
next n

while sum(integer_part(array_numbers())) <> target
if sum(integer_part(array_numbers())) > target
for for n = 1 to max_elements(array_numbers)
if fractional_part (array_numbers(n)) - 0.5 >= bestsofar then
bestsofar = fractional_part (array_numbers(n)) - 0.5
tobezapped = n
end if
next n
array_numbers(tobezapped)=integer_part(array_numbe rs(tobezapped)) 'or you could subtract bestsofar+1
else
'do the sort of opposite to round up the number closest to fractional 0.5
end if
wend

now your answer is integer_part of all the elements in array_numbers

[Mich the Tester]

aye, thats the logic all right. but I want the algorithm

you still haven't found your way to the pub then?

[EternalOptimist]

veeeeeeeeeery quick answer cos hungry and glanced at thread
add all the rounded numbers up
=999

now you've got to loose 1 somewhere so choose the number with the fractional part closest to .5 and > 0.5 and zap it's fractional part

no repeat the adds of the rounded numbers and u get 998.

P.S. There might (probably) is a fairer way to "allocate" the zapping of the extra 1 but what I just scribbled might be a good way

aye, thats the logic all right. but I want the algorithm

[Doggy Styles]

number 998

10% = 100 (rounded up)
30% = 300 (rounded up)
30% = 300 (rounded up)
30% = 300 (rounded up)

for a total of 1000

I can do it the hard way. but is there a simple algorithm ?

As it all boils down to 'reasonableness', there's probably some AI algorithm that would do it for you.

[Olly]

veeeeeeeeeery quick answer cos hungry and glanced at thread
add all the rounded numbers up
=999

now you've got to loose 1 somewhere so choose the number with the fractional part closest to .5 and > 0.5 and zap it's fractional part

no repeat the adds of the rounded numbers and u get 998.

P.S. There might (probably) is a fairer way to "allocate" the zapping of the extra 1 but what I just scribbled might be a good way

[OwlHoot]

HTH,

Joshi.

Not really, Bob, in fact it's practically irrelevant; but thanks for trying.

[Hill Station Murthy]

I have a number and I want to break it down into integers by %

but I want to guarantee that the sum of the breakdown equals the original number. i.e. if there is a rounding error, I want it corrected.

eg

number 998

10% = 100 (rounded up)
30% = 300 (rounded up)
30% = 300 (rounded up)
30% = 300 (rounded up)

for a total of 1000

I can do it the hard way. but is there a simple algorithm ?

In most programming languages there is modulus operator that yiou can use to do you're rounding operations.

Let me show you illustartion.

Number_to_round <modulus operator> reminder_value
for very simple example

if (100 % 2 == 0)
// the number is less than 50 so round down to 0
else
// the number is greater than 50 so round up t o 100

I think from this simple example you should be able to accomodate this in your project and use this with some degree of success.

Let me know if I can be of any further assistance.

HTH,

Joshi.

[MarillionFan]

Piece of piss. Proof is a bit long for posting though.

Fermat.

[EternalOptimist]

I'll summarize for 3 variables, but it works the same for any positive number of these

Suppose your given exact percentages are p, q, r

Let x, y, z be your required integers with sum s

1. Determine x, y, z as floor(p * s / 100), floor(q * s / 100), floor(r * s / 100)

2. If the sum x + y + z is less than s then add 1 to x, y, z successively until
the sum equals s

3. The required solution is whichever of the following minimizes
(X - p * s / 100)^2 + (Y - q * s / 100)^2 + (Z - r * s / 100)^2

X, Y, Z =
x + 1, y - 1, z or
x + 1, y, z - 1 or
x - 1, y + 1, z or
x, y + 1, z - 1 or
x - 1, y, z + 1 or
x, y - 1, z + 1


I think

the number of variables is an unknown
the % will be 2 dp
n will be an integer

[OwlHoot]

I'll summarize for 3 variables, but it works the same for any positive number of these

Suppose your given exact percentages are p, q, r

Let x, y, z be your required integers with sum s

1. Determine x, y, z as floor(p * s / 100), floor(q * s / 100), floor(r * s / 100)

2. If the sum x + y + z is less than s then add 1 to x, y, z successively until
the sum equals s

3. The required solution is whichever of the following minimizes
(X - p * s / 100)^2 + (Y - q * s / 100)^2 + (Z - r * s / 100)^2

X, Y, Z =
x, y, z or
x + 1, y - 1, z or
x + 1, y, z - 1 or
x - 1, y + 1, z or
x, y + 1, z - 1 or
x - 1, y, z + 1 or
x, y - 1, z + 1


I think

For two variables the choice of X, Y would be one of x, y; x-1, y+1; x+1, y-1.

In general one shuffles a 1 between every pair (in either direction) and includes the original set in the test (DOH! I forgot that)