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.
Of course, this is implementation-defined with negative numbers.
rlbond
2010-06-08 21:58:08
@rlbond, I think it will be fixed to being negative for negative numbers in C++0x. @marndt, you misread the question: `number` here is a bigint and the `%` operator is to be defined.
avakar
2010-06-08 22:25:52
-1 because it doesn't really answer his question, he wants to know the best way to implement it for a custom class he's writing, otherwise you're spot on. If you're implementing a Int256 class (as opposed to Int16, Int32, Int64) how do you implement % for said class? You can't use the inherit one because it's only defined for the .NET predefined types.
drachenstern
2010-06-08 22:53:36
@drachenstern: where did the .NET come from? It's a C++ question, and there you can't inherit a predefined one - it's an operator, not a member function.
MSalters
2010-06-09 09:07:40
In general, this is unlikely to be the most efficient way. `BigInt::operator%` needs to accept any input, but `%10` is a special case that allows specific optimizations.
MSalters
2010-06-09 09:09:28
@MSalters ~ whoops, my bad, I didn't mean to make my example so .NET-centric, but the point still holds, modulus has to be defined, so how do you define it for such a data type? I was hoping the concept was transcendent. Just saying "well you would do it by defining the modulus operator" is not enough, his question was more how to define such an operator.
drachenstern
2010-06-09 14:38:56
@drachenstern: actually, I think that defining it for Int256 is fairly trivial when you have an underlying operator% on Int32 (or `unsigned long`, for standard C++). See my post on an optimized case.
MSalters
2010-06-09 14:47:29
@MSalters ~ Yeah, I responded to the above then saw that, you also earned a +1 from me :p ~ However, you actually showed how the op would work, not just "oh run it through modulus" (Specifically, there's more work to it than JUST using the predefined modulus op.)
drachenstern
2010-06-09 14:55:55
+2
A:
Since you're dealing with input, the easiest thing to do would be to read it as a string, and convert the last character to a digit value by subtracting '0'.
Jerry Coffin
2010-06-08 21:55:10
+4
A:
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
MSalters
2010-06-09 09:27:40