Grains

[eklatzer]

Hey, when mentoring Grains (https://exercism.org/tracks/go/exercises/grains) I was asked, why the person must iteration from 0 to 65 and why this works:

func Total() uint64 {
    var total uint64 = 0
    for i := 0; i <= 65; i++ {
        total += uint64(math.Pow(float64(2), float64(i)))
    }
    return total
}

After a bit of debugging I found out, that this is caused by an overflow:

2^62=4611686018427387904     new sum: 9223372036854775807
2^63=9223372036854775808     new sum: 18446744073709551615
2^64=9223372036854775808     new sum: 9223372036854775807  <-- overflow
2^65=9223372036854775808     new sum: 18446744073709551615

When adding 2^65 after the overflow the result is the result that was expected and all tests pass. Is there anything we could do, to detect this, as this is not the expected behaviour as this would be:

func Total() uint64 {
    var total uint64 = 0
    for i := 0; i <= 63; i++ {
        total += uint64(math.Pow(float64(2), float64(i)))
    }
    return total
}

[andrerfcsantos]

That's a good catch. I'm not sure there is really a good way to test for this or even if it's something we want to test.

A possible way to detect this overflow (at least the basic cases) would be to parse the AST of the solution and try to detect loops or shift operations that would cause an overflow, but this is probably something that the analyzer should do and not the tests for the exercise.

However, I'm fine with leaving this sort of overflow discussion to mentoring sessions. It's something that deserves a proper explanation from a mentor, as the student still might be confused and frustrated with a failing test they possibly don't understand. Mentors can also point this out, even if the students don't ask explicitly. We can also mention this in the mentor notes. I'm drafting some things to include in mentor notes for exercises - I made a note to include this for the grains exercise.

[eklatzer]

Do you want me to summarize the problem for the mentor nodes?

[andrerfcsantos]

@eklatzer That would be great! Feel free to message me on slack so we can exchange some notes :)

[eklatzer]

Hey, here is my summary:

Binary numbers and integer overflows

Humans mostly use decimal numbers, so numbers with the base 10. This means that every digit has a value of 10n.

For example for 135: 135=1*10^2+3*10^1+5*10^0

Computers only now the values 1 and 0, or ON and OFF, or HIGH and LOW. Therefore computers use binary numbers with the base 2. Couting up for computers looks like this:

000   // 0
001   // 1
010   // 2
011   // 3
100   // 4
101   // 5
110   // 6
111   // 7

For example for 13: 13=1*2^3+1*2^2+0*2^1+1*2^0=8+4+0+1=13

This means 13 represented for a computer is 1101

For the example 7: 7=1*2^2+1*2^1+1*2^0=4+2+1=7

This means 7 represented for a computer is 111. When adding 1 to this value, humans know it is 8, for a computer it is 1000. As for 7 all digits were already 1 for 8 all previous digits are set to 0 and the next digit is set to 1. Keep this fact in mind for the following example.

var number uint64 = 57
fmt.Printf("%b\n", number)
// Output: 111001

In this case using the type uint64 means, that the computer can store up to 64 bits. A bit is one digit in the binary world, so the previous example 1101 conisted of 4 bits. When using the type uint64 the 64 is the number of bits used for storing variables of this type. The maximum value therefore is 1111111111111111111111111111111111111111111111111111111111111111. When adding 1 we get a so-called integer overflow, as the next digit would be set to 1 but there is no next digit for this data-type. All other digits are set to 0 so the value for the variable now is 0. Example:

var max uint64 = math.MaxUint64
fmt.Printf("%064b\n", max)
// Output: 1111111111111111111111111111111111111111111111111111111111111111
fmt.Printf("%064b\n", max+1)
// Output: 0000000000000000000000000000000000000000000000000000000000000000

Additional sources: Integer overflow

Grains

In the exercise Grains a uint64 is used. Normally the func Total() should sum up the values from 20 to 263:

func Total() uint64 {
    var total uint64 = 0
    for i := 0; i <= 63; i++ {
        total += uint64(math.Pow(float64(2), float64(i)))
    }
    return total
}

This results in 18446744073709551615 which is in binary 1111111111111111111111111111111111111111111111111111111111111111. This is the max value a uint64 can store, so when adding more values, a integer overflow is the result.

When using the following code, which counts to 265, a integer overflow is the result:

func Total() uint64 {
    var total uint64 = 0
    for i := 0; i <= 65; i++ {
        total += uint64(math.Pow(float64(2), float64(i)))
    }
    return total
}

2^62=4611686018427387904     new sum: 9223372036854775807
2^63=9223372036854775808     new sum: 18446744073709551615
2^64=9223372036854775808     new sum: 9223372036854775807  <-- overflow
2^65=9223372036854775808     new sum: 18446744073709551615

As you can see, the result for after summing up to 263 and after summing uo to 265 is the same→all test-cases pass, also if the values are summarized up to 265.

[junedev]

@eklatzer The mentor notes live in this repository/folder: https://github.com/exercism/website-copy/tree/main/tracks/go/exercises It would be great if you could create a PR there. If you feel like it, you can create "full" mentor notes for grains like we have for hamming https://github.com/exercism/website-copy/blob/main/tracks/go/exercises/hamming/mentoring.md. Otherwise, you can also just add the usual headers and write TODO below those and then add your content in some section called Integer Overflow or similar.

When transferring the content, I don't think you need to include the part about how binary works. I think we can assume that mentors and even most students know that.

[eklatzer]

Hey, I think this issue can be closed with #2206, can't it?

[junedev]

Yes, I forgot to link the issue before merging. Thanks for the reminder.