[RESOLVED] Easy math question

[DigiRev]

I suck at math.

There is a ranking system that stores a rating from 1 to 3 (1 being bad, 3 being best).

So there is a list of thousands of ratings all from 1 to 3.

To get an average...add up all the ratings and divide by how many there are (simple enough).

But to display that as a score of 1 to 10, (instead of 1 to 3) how would you do that?

[DigiRev]

Right now, what I'm doing is:

If rating = 3 Then
    Total = Total + 10
elseif rating = 2 then
    Total = Total + 5
Elseif rating = 1 then
    Total = Total + 1
End If

And that seems to be working, is there a better way?

[Shaggy Hiker]

Just for grins, I tried getting rid of the If statement. I ended up with this monstrosity, but when I tested it, DigiRev's solution was in the vicinity of 33 times as fast as this. Frankly, I'm not surprised.

Total += (((rating - 1) * 5) + ((CInt(2 ^ rating) >> 1) And 1))

[anhn]

With linear mapping:
If Avg(rating) = 1 then Score = 1 : x₁ = 1, y₁ = 1
If Avg(rating) = 3 then Score = 10: x₂ = 3, y₂ = 10

You can have an equation:
Score = a*Avg(rating) + b, where a = 4.5 and b = -3.5 :
y = a*x + b
a = (y₂-y₁)/(x₂-x₁),
b = y₁-a*x₁
or:
Score = 4.5*Avg(rating) - 3.5

From that,
If Avg(rating) = 1 then Score = (4.5)*1 - 3.5 = 1
If Avg(rating) = 1.5 then Score = (4.5)*(1.5) - 3.5 = 3.25
If Avg(rating) = 2 then Score = (4.5)*2 - 3.5 = 5.5
If Avg(rating) = 2.5 then Score = (4.5)*(2.5) - 3.5 = 7.75
If Avg(rating) = 3 then Score = (4.5)*3 - 3.5 = 10

[Shaggy Hiker]

There would be a simpler algorithm if the scale was 0 to 10 rather than 1 to 10. It's that 1 that causes trouble.

total+=((rating-1)*5)

That algorithm tests out as being about 30% faster than the If statements.

[Logophobic]

The math is the same regardless of the scales:

Value2 = (Value1 - R1.Low) * (R2.High - R2.Low) / (R1.High - R1.Low) + R2.Low

Which in this case is:
Score = (AvgRating - 1) * 4.5 + 1

This, of course, is exactly what anhn posted:

Score = 4.5 * AvgRating - 3.5

[anhn]

This will overcomes the base 1:

    Total = 0
    For i = 1 To n
        Total = Total + (Rating(i) - 1) * (10 - 1) / (3 - 1)
    Next
    Score = 1 + (Total / n)

or

    Total = 0
    For i = 1 To n
        Total = Total + 1 + (Rating(i) - 1) * (10 - 1) / (3 - 1)
    Next
    Score = Total / n

[jemidiah]

You could do it with fewer multiplication with this:

'Find the average rating (1-3)
    Total = 0
    For i = 1 To n
        Total = Total + Rating(i)
    Next
    AvgRating = Total / n
 
'Map the 1-3 rating to a 1-10 scale to give the overall score
    Score = 4.5 * AvgRating - 3.5

That should be about as fast as it's getting I think.

If you'd like a proof of Anhn and Logophobic's formula I (or I'm sure they) would be happy to prove one.

[anhn]

Agree, that is the formula in post#4 : Score = 4.5*Avg(rating) - 3.5
or post#6 : Score = (AvgRating - 1) * (10 - 1) / (3 - 1) + 1

The code in post#7 just simulates what Shaggy mentioned in post#5 : total+=((rating-1)*5), when he said base-1 has problem.

[Shaggy Hiker]

I was a bit surprised to find that the code posted by Jemidiah is about 30% faster than a simplified version of the If statement approach DigiRev originally posted. In theory, the integer add should be very fast, though all the branches will be potentially costly. However, in VB.NET, integer adds are implemented in a fashion that makes them fairly slow compared to what should be possible, so the advantages of the simple math are non-existent and the cost of the branches are much greater than the additional math required in jemidiah's code.

[jemidiah]

A bit OT, but the original question seems to have been answered, and this is a programming forum after all:

I can understand why the if branches would be slower, but why did they implement integer addition in a way that makes it about as slow as multiplications? That seems really silly.

[DigiRev]

Thanks a bunch. Sorry it took so long to reply (had to go get a root canal ). I like the:

Score = 4.5 * AvgRating - 3.5

And it seems to work great. This is for PHP code so I'm not sure how fast it is (the example I gave was like VB syntax). Speed isn't so much of an issue but I'm sure that is still faster.

I'm not sure how you came up with that 4.5 * AvgRating - 3.5 (my math skills are that bad).

Anyway, thanks.

[Shaggy Hiker]

A bit OT, but the original question seems to have been answered, and this is a programming forum after all:

I can understand why the if branches would be slower, but why did they implement integer addition in a way that makes it about as slow as multiplications? That seems really silly.

The bit about integer addition annoyed the heck out of me when I first discovered it. I had an approximation for the Pythagorean Theorem based on the RISC subset of the instruction set for x86 processors, and decided to test it in VB. It turned out that using the full method, complete with multiplications and square roots, was faster than the integer and bit shifting method. That kind of kills off some optimization options.

By the way, in this case, turning off the integer overflow checks improved the performance of both routines by about 30%, as well, but the benefit was roughly equal for both techniques (actually, I think it helped the branching technique by about 40%, and the mathematical approach by just under 30%).

[anhn]

I like the:

Score = 4.5 * AvgRating - 3.5

And it seems to work great. ...

I'm not sure how you came up with that 4.5 * AvgRating - 3.5 (my math skills are that bad).

In case you may need if you have different scale in the future: How it comes up with 4.5 and -3.5 is explained in post#4 in term of linear equation solving.

Don't be supprise, I used to be a maths teacher for more than 10 years three decades ago.
I did use this method many times when I want to standardize the marks I gave to my students as sometimes a test was too hard and the top student get only 12/20 and I wanted to move that mark up to 18/20; and the lowest mark 3/20 is also moved up to 6/20.
Scale [3 - 12] become Scale [6 - 18].

[jemidiah]

In this case, the formula comes about like this:
You have numbers from 1-3, you want to map them to numbers from 1-10. (1) First shift the numbers from 1-3 to the range 0-2. (2) Now multiply that range from 0-2 by 4.5 to get a range from 0-9. (3) Now shift the range from 0-9 to 1-10.

Algebraically this becomes
(1) A = (AvgRating - 1); A is in the range 1-3 minus 1 = 0-2
(2) B = A*4.5; B is in the range 0-2 times 4.5 = 0-9;
(3) C = B + 1 = Your Answer; C is in the range 0-9 plus 1 = 1-10.

Combine 1, 2, and 3 by substitution to get

C = B + 1 = A*4.5 + 1 = (AvgRating - 1)*4.5 + 1 = AvgRating*4.5 - 4.5 + 1 = AvgRating*4.5 - 3.5 = your answer.


Alternatively, you can think of it as getting the 1 AvgValue to map to 1, and getting the 3 AvgValue to map to 10, using a "linear" map. That is,

f(1) = 1,
f(3) = 10,
f(AvgRating) is linear.

You might remember linear functions from an algebra course. In this context, we know that f must be of a certain form:

f = a*AvgRating+b

where a and b are some constants. If you graph f, you'll see that it ascends or descends smoothly, like your 1-10 rating scale should, which is why we use a linear function here instead of something crazy.


With the above, finding a and b is all algebra:
f(1) = a*1+b = a + b = 1 -> a = 1-b
f(3) = a*3+b = 3a + b = 3(1-b)+b = 3-2b = 10 -> 2b = -7 -> b = -7/2 = -3.5 -> a = 1-(-3.5) = 4.5, so we have

f(AvgRating) = 4.5*AvgRating - 3.5 = your answer.

Anhn and Logophobic used generalizations of this technique which allow the easy scaling from one coordinate system (one linear range) to another. For instance, you can create the Celsius to Fahrenheit conversion formula from this:

Value2 = (Value1 - R1.Low) * (R2.High - R2.Low) / (R1.High - R1.Low) + R2.Low

We're converting from system R1 where we have a low and high end to the scale, as well as a value, to the system R2. Let's convert from Fahrenheit to Celsius, so using limits we know the conversions for,

Freezing Points: R1.Low = 32 deg F, R2.Low = 0 deg C
Boiling Points: R1.High = 212 deg F, R2.High = 100 deg C.

Value1 will then of course be in [answer this yourself first if you wish to truly follow along] the scale that begins with the letter F, and Value2 will be in Celsius. Let's make this more obvious by using these names:

Value1 = F,
Value2 = C.

Then the conversion formula falls out to be

C = (F-32)*(100-0)/(212-32) = (F-32)*100/180 = (F-32)*5/9, which might be a familiar formula to you.

You can check this formula, among other ways, by checking what F = -40 gives. Perhaps you'll recall that F and C scales are actually equivalent at -40 degrees, so C should be -40 here:

C = (-40-32)*5/9 = (-72)*5/9 = (-8*9)*5/9 = -8*5 = -40.

Yay, it works. This same method was used in your case to provide your magical formula, and can be proven using the second explanation from above, or even (if you're a bit more creative) the first explanation.


I hope this helped make the math seem a bit less mystical

[anhn]

The graph below may help to understand a little bit more.

With equation : y = a*x + b

a is the slop of the line: 
    y2 - y1   10 - 1
a = ––––––– = –––––– = 4.5
    x2 - x1    3 - 1

b = -3.5 is the value of y when x = 0

[DigiRev]

Thanks jemidiah and ahn.

I remember learning slopes in basic algebra class (which I hate to admit, but I did not do too well in).

Thanks for explaining it me.