What is the most efficient way to find the last digit of an int in C++

Question

I want to try writing my own BigInt Class so I am wondering what would be the most efficient way to find the last digit of a number in C, especially for an input that would be an extremely large int.

Answer 1

lastDigit = number % 10;

Answer 2

I'm assuming that your BigInt uses a base-256 implementation, but this would work equally well for base-65536 or even bigger bases.

Start with a simple example: BigInt(2828) would be stored as 11*256 + 12. Now BigInt(2828) % 10 = (11*256+12) % 10 = ((11 % 10)*(256 % 10) + 12 % 10)) % 10 = (256 % 10 + 2) % 10 = (6+2) % 10 = 8.

The two basic rules that you'll be applying are (a+b)%10 = (a%10 + b%10) % 10, and (a*b)%10 = (a%10 * b%10) % 10. As it happens, not only is 256 % 10 == 6, but (256^N) % 10 = (6^N) % 10 = 6. This enormously simplifies your LastDigit() function.

So, again assuming a BigInt B represented as a sequence d_N..d_0 with base 256. Then B % 10 is (6*sum(d_i % 10) - 5 * (d_0 % 10)) % 10. Each term in the summation is at most 9, obviously. Hence you can trivially sum (ULONG_MAX/6) base-256 digits without overflowing, and the same still applies to base-65536 and base-4294967296