The Stack Overflow podcast is back! Listen to an interview with our new CEO.
3 replaced http://mathematica.stackexchange.com/ with https://mathematica.stackexchange.com/
source | link

While working on an answer to http://mathematica.stackexchange.com/q/87406/121Count the sequences in an array I found that DigitCount was the bottleneck in my code when used as DigitCount[num, 2, 1]. DigitCount first expands the number to an explicit list of digits and then Tallys them. This is of course quite inefficient.

A minor improvement can be had by simply summing the IntegerDigits but that still wastefully expands the size of the expression more than sixty times.

Is there a faster method to perform this operation on big integers?

A less performance oriented related question: http://mathematica.stackexchange.com/q/15137/121Sum over binary digits of integer


Examples:

num = RandomInteger[10^(3*^6)];
list = IntegerDigits[num, 2];

ByteCount /@ {num, list}
{1245800, 79726416}
DigitCount[num, 2, 1]      // RepeatedTiming
Tr @ IntegerDigits[num, 2] // RepeatedTiming
{0.0417, 4982222}

{0.028, 4982222}

An unrelated bit-level operation is two orders of magnitude faster:

BitShiftLeft[num]; // RepeatedTiming
{0.000264, Null}

While working on an answer to http://mathematica.stackexchange.com/q/87406/121 I found that DigitCount was the bottleneck in my code when used as DigitCount[num, 2, 1]. DigitCount first expands the number to an explicit list of digits and then Tallys them. This is of course quite inefficient.

A minor improvement can be had by simply summing the IntegerDigits but that still wastefully expands the size of the expression more than sixty times.

Is there a faster method to perform this operation on big integers?

A less performance oriented related question: http://mathematica.stackexchange.com/q/15137/121


Examples:

num = RandomInteger[10^(3*^6)];
list = IntegerDigits[num, 2];

ByteCount /@ {num, list}
{1245800, 79726416}
DigitCount[num, 2, 1]      // RepeatedTiming
Tr @ IntegerDigits[num, 2] // RepeatedTiming
{0.0417, 4982222}

{0.028, 4982222}

An unrelated bit-level operation is two orders of magnitude faster:

BitShiftLeft[num]; // RepeatedTiming
{0.000264, Null}

While working on an answer to Count the sequences in an array I found that DigitCount was the bottleneck in my code when used as DigitCount[num, 2, 1]. DigitCount first expands the number to an explicit list of digits and then Tallys them. This is of course quite inefficient.

A minor improvement can be had by simply summing the IntegerDigits but that still wastefully expands the size of the expression more than sixty times.

Is there a faster method to perform this operation on big integers?

A less performance oriented related question: Sum over binary digits of integer


Examples:

num = RandomInteger[10^(3*^6)];
list = IntegerDigits[num, 2];

ByteCount /@ {num, list}
{1245800, 79726416}
DigitCount[num, 2, 1]      // RepeatedTiming
Tr @ IntegerDigits[num, 2] // RepeatedTiming
{0.0417, 4982222}

{0.028, 4982222}

An unrelated bit-level operation is two orders of magnitude faster:

BitShiftLeft[num]; // RepeatedTiming
{0.000264, Null}
2 corrected typo
source | link

While working on an answer to http://mathematica.stackexchange.com/q/87406/121 I found that DigitCount was the bottleneck in my code when used as DigitCount[num, 2, 1]. DigitCount first expands the number to an explicit list of digits and then Tallys them. This is of course quite inefficient.

IA minor improvement can be had by simply summing the IntegerDigits but that still wastefully expands the size of the expression more than sixty times.

Is there a faster method to perform this operation on big integers?

A less performance oriented related question: http://mathematica.stackexchange.com/q/15137/121


Examples:

num = RandomInteger[10^(3*^6)];
list = IntegerDigits[num, 2];

ByteCount /@ {num, list}
{1245800, 79726416}
DigitCount[num, 2, 1]      // RepeatedTiming
Tr @ IntegerDigits[num, 2] // RepeatedTiming
{0.0417, 4982222}

{0.028, 4982222}

An unrelated bit-level operation is two orders of magnitude faster:

BitShiftLeft[num]; // RepeatedTiming
{0.000264, Null}

While working on an answer to http://mathematica.stackexchange.com/q/87406/121 I found that DigitCount was the bottleneck in my code when used as DigitCount[num, 2, 1]. DigitCount first expands the number to an explicit list of digits and then Tallys them. This is of course quite inefficient.

I minor improvement can be had by simply summing the IntegerDigits but that still wastefully expands the size of the expression more than sixty times.

Is there a faster method to perform this operation on big integers?

A less performance oriented related question: http://mathematica.stackexchange.com/q/15137/121


Examples:

num = RandomInteger[10^(3*^6)];
list = IntegerDigits[num, 2];

ByteCount /@ {num, list}
{1245800, 79726416}
DigitCount[num, 2, 1]      // RepeatedTiming
Tr @ IntegerDigits[num, 2] // RepeatedTiming
{0.0417, 4982222}

{0.028, 4982222}

An unrelated bit-level operation is two orders of magnitude faster:

BitShiftLeft[num]; // RepeatedTiming
{0.000264, Null}

While working on an answer to http://mathematica.stackexchange.com/q/87406/121 I found that DigitCount was the bottleneck in my code when used as DigitCount[num, 2, 1]. DigitCount first expands the number to an explicit list of digits and then Tallys them. This is of course quite inefficient.

A minor improvement can be had by simply summing the IntegerDigits but that still wastefully expands the size of the expression more than sixty times.

Is there a faster method to perform this operation on big integers?

A less performance oriented related question: http://mathematica.stackexchange.com/q/15137/121


Examples:

num = RandomInteger[10^(3*^6)];
list = IntegerDigits[num, 2];

ByteCount /@ {num, list}
{1245800, 79726416}
DigitCount[num, 2, 1]      // RepeatedTiming
Tr @ IntegerDigits[num, 2] // RepeatedTiming
{0.0417, 4982222}

{0.028, 4982222}

An unrelated bit-level operation is two orders of magnitude faster:

BitShiftLeft[num]; // RepeatedTiming
{0.000264, Null}
    Tweeted twitter.com/#!/StackMma/status/617093193084108800
1
source | link

Faster binary Hamming weight for big integers?

While working on an answer to http://mathematica.stackexchange.com/q/87406/121 I found that DigitCount was the bottleneck in my code when used as DigitCount[num, 2, 1]. DigitCount first expands the number to an explicit list of digits and then Tallys them. This is of course quite inefficient.

I minor improvement can be had by simply summing the IntegerDigits but that still wastefully expands the size of the expression more than sixty times.

Is there a faster method to perform this operation on big integers?

A less performance oriented related question: http://mathematica.stackexchange.com/q/15137/121


Examples:

num = RandomInteger[10^(3*^6)];
list = IntegerDigits[num, 2];

ByteCount /@ {num, list}
{1245800, 79726416}
DigitCount[num, 2, 1]      // RepeatedTiming
Tr @ IntegerDigits[num, 2] // RepeatedTiming
{0.0417, 4982222}

{0.028, 4982222}

An unrelated bit-level operation is two orders of magnitude faster:

BitShiftLeft[num]; // RepeatedTiming
{0.000264, Null}