2

I have a large integer N < 10^2500. I need to get the number of bits set in its binary representation. The number is given in base 10 in a file. Here's how I'm doing it right now :

I made a class called BigNumber which uses an array to store very big integers.

  1. I am parsing the number into a BigNumber object in base 10.
  2. I am converting said number into base 2^x (using 25 for x now, but what matters is that it is a power of 2). For conversion I use the standard method of division by the base repeatedly until the quotient is 0.
  3. Because the number of bits set in a * 2^x is equal to the number of bits set in a (we can write a as a sum of n powers of 2 and when we multiply by a power of 2 we are going to get n factors so n bits) I just need to calculate the number of bits set in every digit of my number using the SWAR algorithm for x < 32, and them sum them up.

This method works, but it is very slow(takes a very long time for a 2500 digit number), and I am assuming it's because of my implementation of division or base change algorithm.

Here's my whole BigNumber class in C++.

Am I approaching this the right way ? And if so, how can I make it run faster ?

This is for learning, not production code, so I'm not going to use already implemented libraries.

  • hint: modern computers are storing numbers as a power of 8, so you could use it – BЈовић Sep 20 '16 at 14:14
2

You have rather tied your hands by storing your BigNumber in base 10, but I can see the practicalities of doing that, both for input and output and for general debugging.

Division is always slower than you'd expect, so you should create a new BigNumber33554432 class which uses base 2^25 instead of base 10. You only need it to be able to add numbers between 1 and 9 into a BigNumber and to multiply a BigNumber by 10, so it will be really easy to write and fast to execute. Then you can convert your base-10 numbers to base 2^25 by reading the digits from left to right. At each step, multiply your current result by 10 and add the new digit.

Once you have your base-2^25 number then counting bits will, as you say, be quick and easy.

  • I do not understand how that helps. I get the number in base 10 so I'd still need to convert from base 10 to base 33554432 and that's basically what's taking a LOT of time. – Adrian Sep 20 '16 at 14:36
  • Conversion by multiplication in base 33554432 is much, much, much faster than conversion by division in base 10. – Martin Kochanski Sep 20 '16 at 14:42
  • I don't quite understand the process you're describing for converting by multiplication. Can you give an example ? – Adrian Sep 20 '16 at 14:43
  • Nevermind, I get what you're saying now. I'll try it! – Adrian Sep 20 '16 at 14:50
  • It worked and it's as you said, much much much faster :). Thank you! – Adrian Sep 20 '16 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.