How to handle very large number in C

**suryak** · 12-15-2013

I am new to solving algorithm puzzles, thinking to start using C for a while.

One thing I observe in puzzles is they demand very very large numbers (eg: of order 100000 digits number) which drives me crazy. How exactly we should be dealing them?

Solving these puzzles don't give us the luxury to use 3rd party libraries for high level API..

say for instance, we have a number of 1000000 digits, how do we even store and operate on it? One way is to store as character array but this leads to complicated logic and probably not faster either..

Take a look into this simple puzzle: SPOJ.com - Problem PALIN
NOTE: I am not asking for a solution to this. but to give a picture what I am talking about and the questions I am trying to solve.

How do we approach such large data.
Since I am new, any help that lets me get better in solving is appreciated.

Thanks

**Hodor** · 12-15-2013

Well, to use a pre-built solution check out GMP

**grumpy** · 12-15-2013

It depends on what you're doing with the numbers but, in general terms, large numbers may be composed from a set (or an array) of smaller numbers. Then you need to design a set of rules for acting on that array to get the results you need.

Think about how you handle large decimal values. They are represented using a string of single digits. Basic operations like addition, subtraction, division, multiplication are executed as a set of operations involving smaller values and some rules.

Finding a palindrome is simply determining if the sequence of digits reversed is the original sequence.

**Hodor** · 12-15-2013

Originally Posted by grumpy

Finding a palindrome is simply determining if the sequence of digits reversed is the original sequence.

The question on SPOJ is kind of more difficult though; the smallest palindromic number > k. I'm not sure how to approach it yet.

**suryak** · 12-15-2013

Finding a palindrome is easy.. I agree get a look at the question:
For a given number n: we need to find next smallest number. If n=100, 101 is next palindrome.

What we typically do is:
1. take the number
2. Increment by 1 for each iteration
3. Reverse each incremented number and see if its a palindrome (another inner loop)

This is more probably O(n^2).. This method takes more execution time

Another implementation I thought:

1. take the number
2. Iterate from 0 to L/2 or (L-1)/2 (L = number of digits)
3. For each iteration from Left-to-Right, we replace a number from Right-to-Left

Ex: n=8133
step1: 8133 --> 8138

4. if left number < right number, increment the number by 1 (at the respective position) and replace
In case if the number is 9 and returns 0, passing 1 towards another number, iterate back by i-1

step2: 8138 --> 8228

I wrote mathematical logics for replacing and incrementing number..
which typically gives us the solution to O(n)

This time I see the solution is raising Errors which I feel are due to not able to handle large numbers.

**grumpy** · 12-15-2013

Well ... there is always the naive search (keep incrementing until you find a palindrome). However, if you want to be a little smarter (and more efficient) I'll describe a couple of steps.

First step: Simply reverse the first half of the digits and append to form a palindrome. If that is greater than your input value you're done. For example: 2881: reverse the digits 28 to form 2882. Done. 28567 reverse the digits 28 to form 28582. Done.

The catch is that, depending on input, doing the above may result in a value less than input. So 182 would lead to 181. In that case, we come to ...

Second step: increment the middle digit (or pair of middle digits if the total number of digits is even) to get 191. Done. This will work, since incrementing earlier digits would result in larger values.

I haven't thought about it enough to work out if there are cases that will be missed with the above steps. But that should be enough to get you started.

**c99tutorial** · 12-15-2013

If you want to use a library to manage big numbers, there are is also the following library which has examples:

BigDigits multiple-precision arithmetic source code

**Adak** · 12-15-2013

Originally Posted by c99tutorial

If you want to use a library to manage big numbers, there are is also the following library which has examples:

BigDigits multiple-precision arithmetic source code

You can't use a library on SPOJ problems.

You don't submit an executable, you submit a source code. The code is then compiled on one of two clusters which have no special libraries.

You can work with large numbers (even this large), with char arrays. The trick is to set up your program so it does the least amount of iterations, no matter what the input.

**c99tutorial** · 12-15-2013

Originally Posted by Adak

You can't use a library on SPOJ problems.

I'm not familiar with SPOJ. What is that. Anyway, of course some libraries must be supported. Otherwise even printf wouldn't work. Even if you don't use an external library, you could study it to gain ideas of how to solve the problem you intend to solve. So, this response is generally not helpful.

**stahta01** · 12-15-2013

Originally Posted by c99tutorial

I'm not familiar with SPOJ.

Sphere Online Judge (SPOJ)

**Adak** · 12-15-2013

Originally Posted by c99tutorial

I'm not familiar with SPOJ. What is that. Anyway, of course some libraries must be supported. Otherwise even printf wouldn't work. Even if you don't use an external library, you could study it to gain ideas of how to solve the problem you intend to solve. So, this response is generally not helpful.

The cluster that will be running (testing) the source code that you submit, has nothing but standard C libraries.

How about that, helpful now?

You don't need to study external libraries - if you work it out by hand a few times, and think about how to minimize the search for the palindrome, you'll do fine.

The naive approach won't work in any of these problems.

**c99tutorial** · 12-15-2013

OP never mentioned palindromes, only large numbers. For palindromes I would say a string representation is the best.

As for libraries, I prefer using them if they are helpful. There is no need to run the described problem on a cluster anyway. A normal computer will do just fine.

**Adak** · 12-15-2013

Originally Posted by c99tutorial

OP never mentioned palindromes, only large numbers. For palindromes I would say a string representation is the best.

As for libraries, I prefer using them if they are helpful. There is no need to run the described problem on a cluster anyway. A normal computer will do just fine.

Yes, he did mention palindrome:

suryak

Finding a palindrome is easy.. I agree get a look at the question:
For a given number n: we need to find next smallest number. If n=100, 101 is next palindrome.

What you or I would use, is irrelevant here. The testing WILL BE DONE BY ONE OF TWO CLUSTERS, by SPOJ, not on any other computer.

**Hodor** · 12-16-2013

I still don't agree that it's an easy problem.

What is the smallest palindromic number greater than, say,

63478194618764184154109571075165168
51856175618561517501985901751865165
71695617658165719519750759817581759
17591674897487487947984797497487478
49784747562487284714617648018642443

**tabstop** · 12-16-2013

63478194618764184154109571075165168
51856175618561517501985901751865165
71695617658165719 are the first half of the numbers, then a 5. Reverse those first seventeen numbers and put them at the end after the 5; since that would start 917... which is bigger than the 197 that was there so you're done.

Thread: How to handle very large number in C

Thread Tools

Search Thread

Display

How to handle very large number in C

Similar Threads

handle large array size 1000000000

Storing a very large number

reading large number

Need help representing a very large number

Large number library?

Tags for this Thread