0

So I tried to make a program that is about Multiplication Consistency. However, that required me to use large numbers. I decided to implement my own structure for handling them, as I thought it would be better to use something customized for the program. But I managed to design two ways to handle big numbers, and I do not know which is better for this case.

The program does a lot of divisions and number generation, without too much printing.

Number generation is done by taking a number, that is the multiplication of powers of 2, 3, 5 and 7 (2^a * 3*b * 5^c * 7^d) and generates all numbers, where the multiplication of the digits equals that number, excluding numbers containing 1s, because such digits can be added infinitely. Generation here is handled recursively, so I do not generate new numbers from scratch.

Once a number is generated, it is tested by which powers of 2, 3, 5 and 7 it is divisible, which is where the program does the divisions. This is where most of the program's work is done.

So, I came up with two ways to handle numbers: a straightforward string of single digits and the structure n * INT + k (n times the max integer value plus a smaller number; INT does not have to be explicitly int32).

Which would be faster?

Digits array:

  • Each digit is a number, so working with the string is working with numbers
  • Printing is as simple as printing an array
  • Division can be done with integers up to 9, or with other strings
  • The more digits, the longer the division process
  • Numbers are easy to build
  • Practically no limit to the length of the number
  • Testing if the number is divisible by some numbers (3, 9, 2^n and 5^n) can be sped up by looking at the digits, but that can become complex to implement

Division with this solution is done by scanning the array.

n * INT + k
  • The structure is about values
  • Printing requires to turn the values into a digit string
  • Division can be done with integers up to the maximum value, and each division makes the number smaller for further divisions
  • The larger the values, the slower the process
  • Numbers require a special algorithm to build
  • Maximum value is INT * INT + INT, so going around that limit would require further development
  • No digits, so testing for divisibility is done by dividing

Division of this structure is recursive: The result of the division is (n / d) * INT + k / d with a remain of (n % d) * INT + k % d. The remain is a number on its own, so it is further divided and the new result is added to the first.

I must note that I have not implemented dividing big numbers by big numbers, so big numbers get divided only by integers.

While the array of digits requires a lot of scanning while dividing, the other option can be slow at first, but the number can be tested for division with much larger numbers, which can quickly lower the value, and such divisions are faster on their own.

How are the two solutions compared?

AlexSavAlexandrov
  • 858
  • 2
  • 13
  • 34
  • I suggest that you read the manual for GNU MP, particularly the internals section. https://gmplib.org/manual/ – Sneftel Aug 01 '19 at 11:07
  • "I decided to implement my own structure for handling them, as I thought it would be better to use something customized for the program" - have you looked into big number libraries in your target language and found a good reason why each of those *won't* work for you? It's almost always better to go with a standard library than to build your own, and building your own is always an option later if the need arises. But it can be an interesting challenge to build it. – Bernhard Barker Aug 01 '19 at 11:22
  • What exactly do you mean by `n * INT + k`? If it means something similar to having an array `[a, b, c, d]` to represent `a*INT^3 + b*INT^2 + c*INT + d`, then that's basically the same as the string approach with `INT = 10` (minus the ASCII conversion). Or do you mean you only have max 2 numbers, i.e. `[a, b]`? But that would still be the same thing though. – Bernhard Barker Aug 01 '19 at 11:25
  • Related / duplicate: [How to Code a Solution To Deal With Large Numbers?](https://stackoverflow.com/questions/1991175/how-to-code-a-solution-to-deal-with-large-numbers) and [How to implement big int in C++](https://stackoverflow.com/questions/269268/how-to-implement-big-int-in-c) – Bernhard Barker Aug 01 '19 at 11:31
  • I decided to write my own solution, for both the challenge and because I want to implement as much functionality as I need. Even now, I think I may have written more code than needed. n * INT + k is how I represent the value of a number. For example, if INT = 2147483647, then 10 = 0 * INT + 10, 9000000000 = 4 * INT + 410065412. This way I do not have to work with an array, but with three values. – AlexSavAlexandrov Aug 01 '19 at 15:02
  • @AlexSavAlexandrov So you won't be able to represent a value >= `(MAX_INT_SIZE+1) * INT` (where `MAX_INT_SIZE` is the maximum integer allowed in the language you're using)? – Bernhard Barker Aug 01 '19 at 15:19
  • As I pointed out in the question - yes, and I may work on that later. – AlexSavAlexandrov Aug 01 '19 at 16:41
  • It looks like you have a problem that has a simpler approach but you are struggling and asking about how to deal with a complicated approach that you selected. In case that is what is happening to you: Note that to "generates all numbers, where the multiplication of the digits equals that number" you don't need to do divisions and multiplications of numbers. – embeddedPy Aug 01 '19 at 20:46
  • For the program, yes, I am implementing more than needed. But while working on it I started thinking about handling large numbers in general. – AlexSavAlexandrov Aug 08 '19 at 12:09

0 Answers0