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/

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

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}

1

# 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}