-2

I was wondering how would you convert an arbitrary length integer integer in some base b represented by a string into a string representation in base 10.

To give you an example, if I send the string "4552" and I also send that it's in base 8, and I want to convert this string into base 10 and return the string but I can't use things like atoi or strtol because if I'd send 312434324324324324324324 It'd be impossible, I first thought you can use like a classical recursive algorithm that do a recursive with the number % 10 until last digit, then reversely putting the number into a string.

Anyway, I'm actually kind of lost and I don't know how is that possible, if you guys have any hints or ways I can do it. I let you the prototype of my function so that you can have the basics, thanks.

char *to_base_10(char *nb, int base)
{
    int size = my_strlen(nb);
}
Clifford
  • 88,407
  • 13
  • 85
  • 165
Chetrit
  • 33
  • 2
  • 8
  • 2
    If you want to work with numbers of arbitrary length without extra libraries, then you will have to recall the pen-and-paper methods taught in the middle school and implement these. – Eugene Sh. Oct 29 '19 at 16:57
  • avoid using recursion, and go for the iterative one from the start. because infinitely long numbers will hit a stack overflow on non-inifinitely large stacks. – Shark Oct 29 '19 at 16:58
  • as I said It is truly not the aim to convert into a number or a long or whatever, and if I put a number like "42343243243243324432343243432432432423432432......" you'll not be able to convert it into a base, I mean without passing by a conversion into any type of long number that you want, here's my question. – Chetrit Oct 29 '19 at 16:59
  • 1
    Computers don't deal with infinite data. Do you mean "unlimited length" rather than infinite? – aschepler Oct 29 '19 at 17:00
  • Thank you @EugeneSh. and Shark for the advises, what do you mean by this old pen-and_paper method, what do I'm supposed to try ? – Chetrit Oct 29 '19 at 17:01
  • https://www.rapidtables.com/convert/number/base-converter.html – Shark Oct 29 '19 at 17:01
  • @aschepler yeah for sure, like the numbers I said in the examples, not an infinite value. – Chetrit Oct 29 '19 at 17:01
  • I don't get it. Then number `4552` is already in base 8. The number `312434324324324324324324` is also in base 8, from what I understand. – KamilCuk Oct 29 '19 at 17:01
  • @Shark I know how to convert a number into a other base, but when you don't have a type int but a char * instead ? – Chetrit Oct 29 '19 at 17:02
  • @KamilCuk yes actually, but my aim is to convert this number from base 8 to base 10 – Chetrit Oct 29 '19 at 17:03
  • 1
    By pen-and-paper I mean the so-called "long addition" and friends. But for your application you might get away without these friends with addition only. – Eugene Sh. Oct 29 '19 at 17:05
  • 1
    _"by infinite I mean way larger than a long or a long long,_" - so _not_ infinite then! Why don't you just say "_arbitrary length integer_" – Clifford Oct 29 '19 at 17:06
  • For the past few days, just for fun, I've been converting the 1,000 digits of pi that I downloaded from the net somewhere, into ~3,000 bits of binary. Kind of a neat challenge. I used an arbitrary-precision arithmetic library which I had written years ago. (But it was silly of me to write one; sane programmers use one that's already written, like GMP.) – Steve Summit Oct 29 '19 at 17:07
  • @HighPerformanceMark, that won't work if `8^veryBig` won't fit in `anynumber_of_bits`. He is looking for a method that is independent of any integral type implementation. – Paul Ogilvie Oct 29 '19 at 17:10
  • 1
    If you are doing this for fun, you would try harder or give up, if this is an assignment, you cannot expect more that a push in the right direction to get you started. – Clifford Oct 29 '19 at 17:12
  • If you're on a Unix or Linux machine (or a Mac), you can type `dc`, then `8 i`, then your base-8 number (as many digits as you want), then `p`, and it will print the base-10 representation, just like that. And then you can write your own code to do that, either using a library like GMP, or by rolling your own. (Some day I'm going to write a tutorial on writing your own arbitrary-precision arithmetic library, because it'd be a great learning exercise, but I haven't written it yet, sorry.) – Steve Summit Oct 29 '19 at 17:12
  • Ok guys, I think I found a solution, after asking to a friend that have a lot of experience : since a base is the sum of each digit multiplied by the base at the power of i (1 , 2 , 3 ....), if you want to do this, you have to code a function that do an infinit addition (which is possible), a function that do an infinit mult, then with this infin_mult function you'll do an infin't pow function, and then you can just do the operations using your infin_operation functions, so you'll have a string in the base you wanted, thank's anyway for those who've tried to help me ! – Chetrit Oct 29 '19 at 17:17
  • There are some classic, classic, very easy algorithms for converting integers to and from their base-b digit representations. The Standard C library already has `atoi` (base 10 only) and `strtol`, and some C libraries have `itoa` to go in the other direction. First learn how to write these using ordinary arithmetic, and working with numbers that will fit in an `int`. (It's all simple addition and subtraction, and multiplication and division by 10, or by **b** if you're working in base b.) Then, to work with numbers bugger than will fit in any `int`, rewrite using GMP for arithmetic. – Steve Summit Oct 29 '19 at 17:17
  • @Chetrit : You are allowed to answer your own question, which is preferable to adding a comment with an answer - SO is not a discussion forum after all. That said, your solution is pretty much what I have advised in my answer - feel free to accept it ;-) – Clifford Oct 29 '19 at 18:01
  • @SteveSummit; I would assume that if there are constraints imposed on the functions he can use, then this is an academic exercise and using GMP is probably equally prohibited. – Clifford Oct 29 '19 at 18:03
  • yes totally @Clifford I can only use my own function, but no problem I already have a whole big lib except the hardest ones like printf that I'll be doing later on ! Thank you – Chetrit Oct 29 '19 at 18:13
  • 1
    Answered [here](https://stackoverflow.com/a/71893738/18765627), converted **Fibonacci(1500000)** for testing. – Michel Apr 16 '22 at 12:18

1 Answers1

1

For an unsigned numeric string n of length L containing base b digits, the "pen & paper" solution is:

ndec = n0 x bL-1 + n1 x bL-2 + ... + nL-1 x b0

(where n0 is the most-significant - i.e. left-hand - digit and nL-1 the least-significant digit - i.e. subscripts are same as a C array order).

So breaking it down into operations you need to implement arbitrary length integer operations for:

  • Exponentiation (xy)
  • Multiplication
  • Addition

Since at its most crude (and I suggest you start there) multiplication can be performed by repeated addition and exponentiation by repeated multiplication, you only need to implement addition. Performance refinements, such a long multiplication and exponentiation by squaring might wait until you have the fundamentals (and determined that the simple solution is even too slow).

So the "pen & paper" solution to addition is relatively straightforward (for A + B iterate digits from n = LSD to MSD+1 performing An + Bn + Carryn-1), and can be implemented in code for arbitrary length strings.

From that, implement multiplication by repeated addition (initially), an in turn exponentiation by repeated multiplication.

Then finally implement the to-decimal expression ndec = ... as above by iteration from n0 to nL-1 using your arbitrary length integer operations.

Validate a few short test strings, then if necessary optimise by more sophisticated multiplication and exponentiation methods, testing this improvements against you original validates test data.

Clifford
  • 88,407
  • 13
  • 85
  • 165
  • @Chetrit : You are welcome. However SO guidelines discourage "thanks" comments - there really is no need. – Clifford Oct 29 '19 at 18:13