Can this implementation of Damm algorithm be optimized?
Nestor via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Thu Feb 9 11:39:49 PST 2017
On Thursday, 9 February 2017 at 18:34:30 UTC, Era Scarecrow wrote:
> On Thursday, 9 February 2017 at 17:36:11 UTC, Nestor wrote:
>> I was trying to port C code from the article in Wikiversity
>> [1] to D, but I'm not sure this implementation is the most
>> efficient way to do it in D, so suggestions to optimize it are
>> welcome:
>>
>> import std.stdio;
>>
>> static immutable char[] QG10Matrix =
>> "03175986427092154863420687135917509834266123045978" ~
>> "36742095815869720134894536201794386172052581436790";
>>
>> char checkDigit(string str) {
>> char tmpdigit = '0';
>> foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') +
>> (tmpdigit - '0') * 10];
>> return tmpdigit;
>> }
>
> Well one thing is you can probably reduce them from chars to
> just bytes, instead of having to subtract you can instead add
> at the end. Although unless you're working with a VERY large
> input you won't see a difference.
>
> Actually since you're also multiplying by 10, you can
> incorporate that in the table too... (although a mixin might be
> better for the conversion than by hand)
>
>
> static immutable char[] QG10Matrix = [
> 00,30,10,70,50,90,80,60,40,20,
> 70,00,90,20,10,50,40,80,60,30,
> 40,20,00,60,80,70,10,30,50,90,
> 10,70,50,00,90,80,30,40,20,60,
> 60,10,20,30,00,40,50,90,70,80,
> 30,60,70,40,20,00,90,50,80,10,
> 50,80,60,90,70,20,00,10,30,40,
> 80,90,40,50,30,60,20,00,10,70,
> 90,40,30,80,60,10,70,20,00,50,
> 20,50,80,10,40,30,60,70,90,00];
>
> char checkDigit(string str) {
> char tmpdigit = 0;
> foreach(chr; str) tmpdigit = QG10Matrix[(chr - '0') +
> tmpdigit];
> return (tmpdigit/10) + '0';
> }
OK I changed the approach using a multidimensional array for the
matrix so I could ditch arithmetic operations altogether, but
curiously after measuring a few thousand runs of both
implementations through avgtime, I see no noticeable difference.
Why?
import std.stdio;
static immutable ubyte[][] QG10Matrix = [
[0,3,1,7,5,9,8,6,4,2],[7,0,9,2,1,5,4,8,6,3],
[4,2,0,6,8,7,1,3,5,9],[1,7,5,0,9,8,3,4,2,6],
[6,1,2,3,0,4,5,9,7,8],[3,6,7,4,2,0,9,5,8,1],
[5,8,6,9,7,2,0,1,3,4],[8,9,4,5,3,6,2,0,1,7],
[9,4,3,8,6,1,7,2,0,5],[2,5,8,1,4,3,6,7,9,0],
];
static int charToInt(char chr) {
scope(failure) return -1;
return cast(int)(chr - '0');
}
ubyte checkDigit(string str) {
ubyte tmpdigit;
foreach(chr; str) tmpdigit =
QG10Matrix[tmpdigit][charToInt(chr)];
return tmpdigit;
}
enum {
EXIT_SUCCESS = 0,
EXIT_FAILURE = 1,
}
int main(string[] args) {
scope(failure) {
writeln("Invalid arguments. You must pass a number.");
return EXIT_FAILURE;
}
assert(args.length == 2);
ubyte digit = checkDigit(args[1]);
if(digit == 0) writefln("%s is a valid number.", args[1]);
else {
writefln("%s is not a valid number (but it would be,
appending digit %s).",
args[1], digit);
}
return EXIT_SUCCESS;
}
More information about the Digitalmars-d-learn
mailing list