Sign in to follow this  

Help finding error in base 62 converter

This topic is 1106 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been working on an encryption system for a program, and as a means of getting size of the encrypted String down, I decided to allow the system to put numbers into any base - 62 being the max (values going 0-9,A-Z,a-z). I wrote this out fairly quickly, and it works for the most part, but *almost* every output value is off on the last character (even worse if not using base 62).
 
Some example cases:
  • 30400066288418849 becomes 2FEQDJkH9F instead of 2FEQDJkH9E (a difference of 1)
  • 21392905688514741 becomes 1Zyk6HmZO9 instead of 1Zyk6HmZO8 (a difference of 1)
  • 22236810928128038 becomes 1dqNWdRcwg instead of 1dqNWdRcwi  (a difference of -2)
  • 1407619700686911 becomes 6Rhvv3b0J, which oddly is right?

As of right now, my code is this:

private static final String toBase( long number, byte radix ){
	if ( !validRadix( radix ) )
		throw new IllegalArgumentException("Illegal value for radix. Cannot convert.");	

	String str = "";
	boolean isNegative = false;
	
	//Before we start, let's do a super quick check to see if nothing changes.
	if (radix == 10 || number == 0 || number == 1)
		return (number + "");
	
	if (number < 0){
		isNegative = true;
		number *= -1;
	}
	while ( number > 0 ) {
		byte times = (byte) (number%radix);
		char c;
		//digit value to char conversion
		if (times < 10)
			c = (char) ('0' + times);
		else if (times < 36)
			c = (char) ('A' + (times - 10));
		else
			c = (char) ('a' + (times - 36));
		str = c + str;
		
		//Then we end our iteration by preparing for the next highest digit.
		number /= radix;
	}
	if ( isNegative )
		str = '-' + str;
	return str;
}
I'm sure it's just a small error somewhere, or a tiny oversight, but I've been looking at it on and off for 5 days and still can't see it. System.out.println()-ing each step hasn't been too informative either, as the math seems about right. The digit conversions are all correct too (6=6, 35=Z, 44=i, 61=z, etc).I've been using this site and this one as a means to test my results. Both have the same results, so I think I'm the wrong one here.
 
Any help is greatly appreciated! Cheers! smile.png
Edited by epicpunnum

Share this post


Link to post
Share on other sites

 

I've been working on an encryption system for a program, and as a means of getting size of the encrypted String down, I decided to allow the system to put numbers into any base - 62 being the max (values going 0-9,A-Z,a-z). I wrote this out fairly quickly, and it works for the most part, but *almost* every output value is off on the last character (even worse if not using base 62).
 
Some example cases:
  • 30400066288418849 becomes 2FEQDJkH9F instead of 2FEQDJkH9E (a difference of 1)
  • 21392905688514741 becomes 1Zyk6HmZO9 instead of 1Zyk6HmZO8 (a difference of 1)
  • 22236810928128038 becomes 1dqNWdRcwg instead of 1dqNWdRcwi  (a difference of -2)
  • 1407619700686911 becomes 6Rhvv3b0J, which oddly is right?

[...]

 

I'm sure it's just a small error somewhere, or a tiny oversight, but I've been looking at it on and off for 5 days and still can't see it. System.out.println()-ing each step hasn't been too informative either, as the math seems about right. The digit conversions are all correct too (6=6, 35=Z, 44=i, 61=z, etc).I've been using this site and this one as a means to test my results. Both have the same results, so I think I'm the wrong one here.
 
Any help is greatly appreciated! Cheers! smile.png

 

I've checked all four of them with Matlab and all input numbers convert to what you say your code produce and not what you expect. You can easily see that your expectation for the first two are incorrect: 9 and 1 from the inputs are odd, but E and 8 from your expectations are even, and thus your expectations cannot be correct. However, F and 9 from the values your code produce are indeed odd values.

 

I tried the converter code in your last link and 30400066288418848, 30400066288418849 and 30400066288418850 all convert to 2FEQDJkH9E, while 30400066288418851 converts to 2FEQDJkH9I. Without looking at that code, I suspect that they are doing the calculations with 64-bit floating point values. Since they only have 53 bits of precision and 30400066288418849 in on the order of 54 bits, there simply isn't enough precision to do precise integer calculations at those magnitudes.

 

In short, your code produces the correct values (not saying there aren't other corner cases where it may be wrong, just that you examples are correct), and your links are not precise enough for your values.

Edited by Brother Bob

Share this post


Link to post
Share on other sites

The sites are the ones in the wrong. They're probably implemented in javascript, which I believe treats all numbers as floats, and thus are losing precision. As an example, your third number, punched into windows calc, as the first step would be:

 

22236810928128038 % 62 = 42, which should be 'g'. If we subtract 42 out of there, we get 

22236810928127996, which on the second site properly ends up with a final digit of '0'. If you give it 22236810928127997, it still ends in '0', and if you give it 22236810928127998, it jumps to '4'. double precision floats only give about 16 digits of precision, so feeding it an 18 digit number means it starts rounding in units of 4.

 

The entire idea seems a bit odd however, as for this to be reasonable, you have to convert before encrypting, and need to know exactly where numbers live in the output to parse them back properly. It seems like it would be better to encrypt directly from binary, and base-64 convert the output if you need to send it over a restricted channel.

Share this post


Link to post
Share on other sites

Oh man, that's a huge weight off of my shoulders haha. Thanks Brother Bob and ReaperSMS!

 

I didn't even consider the fact that both languages use floating points behind the scenes. I'll mark it down as solved :)

Share this post


Link to post
Share on other sites

This topic is 1106 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this