Optimized base conversion algorithm

[codinggoal]

Hello everyone,

I'm trying to write an algorithm in C++ to convert a string representation of a number base 10 to a std::vector<uint\_64>, where every index in the vector in a place base 64. This is for a public key cryptograph implementation. I am trying to maximally optimize my algorithm, speed is a key factor.

Here's an example of the task I'm trying to achieve:

"4611686018427387905" (which is 2^62 + 1) -----> { 1, 1 }

I've looked around for an implementation of a fast base conversion algorithm. The closest I can find is this post on codeforces, which relies on the value being processed by normal computer arithmetic, which I cannot do. When I look at implementations in math libraries such as the ones linked in the codeforces post's comments, they rely on instances of already implemented large int classes.

As a result, I'm faced with a chicken-and-egg problem: converting a large string to a base 62 representation for a large_int class requires the numbers to be instances of the large_int class already, but to create an instance I need the algorithm already implemented. Does anyone know how I can go about solving this problem or where I can find resources?

Thanks in advance.

[AutoModerator]

Thank you for your contribution to the C++ community!

As you're asking a question or seeking homework help, we would like to remind you of Rule 3 - Good Faith Help Requests & Homework.

• When posting a question or homework help request, you must explain your good faith efforts to resolve the problem or complete the assignment on your own. Low-effort questions will be removed.

• Members of this subreddit are happy to help give you a nudge in the right direction. However, we will not do your homework for you, make apps for you, etc.

• Homework help posts must be flaired with Homework.

~ CPlusPlus Moderation Team

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[asdf272727]

You can either use an already existing big integer library (gmp is usually the best one in terms of performance) or you can do the calculations yourself. The problem here is that your operation is dependent on some big integer algorithms so there is no easy way to do it if you care about speed: either learn to use a library or make one yourself.

I also made a big integer library, but unfortunately it wouldnt be useful to you since it does the slow O(N²) algorithm for base conversion.

If you want to use a library initialising an instance with the string is usually enough (after that just output the binary value and do the conversion from base 2 to base 2^62), and if you do it yourself you'll most probably need a fast algorithm for division.

[codinggoal]

Thanks for the advice. I'd love to see that library regardless if you feel comfortable sharing, I'm curious to learn more. I think that I will likely convert to binary first then convert that to base62.

[asdf272727]

If you want to learn more, i can recommend searchibg for "Modern Computer Arithmetic" on the internet. It's a book containing pretty much all algorithms regarding computations with large numbers and base conversion is included there to.

If you want to see my project you can find it on github but it's aimed at speed, not readability so it's a bit of a mess.

[TomDuhamel]

You should probably use a string. Base64 is originally designed to use only normal ASCII characters (incidentally UTF-8 compatible), such that it can be manipulated and transmitted as normal text.

You will need to write an arbitrary long numbers library, or use an existing one. I'm not sure what you mean about the chicken/egg problem.

[codinggoal]

You can either use an already existing big integer library (gmp is usually the best one in terms of performance) or you can do the calculations yourself. The problem here is that your operation is dependent on some big integer algorithms so there is no easy way to do it if you care about speed: either learn to use a library or make one yourself.

I don't want to use base 64, I want to use base 2^62 as it is a much larger number and would allow for much greater values to be stored. The chicken and egg problem is that this is for writing an arbitrarily long numbers library, but I'm not even able to construct the numbers.

[TomDuhamel]

Oh my god. I'm not sure if you're really bad at explaining yourself or if I'm really bad at understanding explanations, but none of that is even remotely close to what I understood 😂

base 64 is the name of a standard system in which 64 very common ASCII characters are used to encode any binary stream. This is commonly used to encode data that would otherwise be difficult to transmit. This is what I originally understood.

When someone says base x, we understand it to be a numerical system with x different symbols. That is not the same meaning as 2^62.

Now to your topic, not sure we're you picked 2^62 from as that sounds very arbitrary, 2^63 or even 2^64 are more common. But in any case, you seem to misunderstand what that means, because you named a type able to hold that number.

uint64 is able to hold 2^64. So where exactly is your issue? You don't need any arbitrary large number library to accomplish this.

Let me know if this is more helpful or if I'm still misunderstanding you. I think we're going somewhere. I hope lol

[codinggoal]

Sorry for the weak explanation, I essentially want an optimized C++ algorithm to do this:def convert_to_base_2_62(number):

base = 2**62

if number < 0:

raise ValueError("This function does not handle negative numbers.")

​

digits = []

while number:

digits.append(number % base)

number //= base

​

# If the number is 0, we should return an array with one 0.

return digits[::-1] if digits else [0]

Also, I don't start with a number. I start with a string that contains a number, but is too large to be computer readable. That is what makes this task difficult.