On computing the checksum

Problem

Marius Bancila [Bancila 2018](Chapter 8, Problem 69) describes a checksum computation problem which can be paraphrased as follows:
Let X = x1x2…xN
where xi is a decimal digit.
X is a valid number if

i=0N (N-i+1)*xi) mod 10 = 0

Naive Solution

A function to compute the checksum is shown below in C++ syntax

int checksum(const string& number)
{
    auto index = number.length();
    auto sum = 0;
    auto K = -1;
    for(auto c: number){
        ++K;
        sum = index *(c-'0');
        --index;
    }
    return sum%10;
}

Loop invariant:


Here K is the index of the loop and N is the length of the string. Notice that K is redundant and included only for the purpose of the proof

However one could avoid the multiplication by using the following routine:

int my_checksum(const string& number)
{
    auto s0 = 0;
    auto sum = 0;
    auto K = 0;
    for(auto c: number){
        s0 += (c - '0');
        sum +=  s0;
        ++K;
    }
    return sum%10;
}

Loop invariant:


Once again N is the length of the string.

Explanation

In case the correctness of the solution is not obvious, notice that the sum can be computed as follows


x1 +
x1 + x2 +
...
x1 + x2 + ... + xN

Notice that x1 is added N times, x2 is added N-1 times and so on. Thus in my_checksum, s0 computes a single row while sum accumulates all the rows computed

Reference
[Bancila 2018] Marius Bancila “The Modern C++ Challenge” Packt Publishing Birmingham-Mumbai 2018.

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s