C Fast base convert from decimal to ternary

Question

is there any method of changing decimal number to ternary ? I mean i don't want to use modulo and divide method, i have very big decimal number, something like 128123832812381835828638486384863486.............1237127317237 and so on.

Also don't want to use bigints.

Is there any method ?

Answer 1

You don't have to use divide/modulo. Instead, iterate over the input digits, from low to high. For each digit position, first calculate what 1000....000 would be in the output representation (it's 10x the previous power of 10). Then multiply that result by the digit, and accumulate into the output representation.

You will need routines that perform multiplication and addition in the output representation. The multiplication routine can be written in terms of the addition routine.

Example:

Convert 246 (base-10) to base-3.

Start by initialising output "accumulator" a = "0".

Initialise "multiplier" m = "1".

Note also that 10 is "101" in the output representation.

First digit is 6, which is d = "20".

• Multiply: t = d * m = "20" * "1" = "20".
• Accumulate: a = a + t = "0" + "20" = "20".
• Update multiplier: m = m * "101" = "1" * "101" = "101".

Second digit is 4, which is d = "11".

• Multiply: t = d * m = "11" * "101" = "1111".
• Accumulate: a = a + t = "20" + "1111" = "1201".
• Update multiplier: m = m * "101" = "101" * "101" = "10201".

Third digit is 2, which is d = "2".

• Multiply: t = d * m = "2" * "10201" = "21102".
• Accumulate: a = a + t = "1201" + "21102" = "100010".

So the answer is "100010".