10

Maybe this doesn't belong on SO but I don't know where else.

I have to reimplement printf(3) with C without using any function that would do the conversion for me, I'm nearly done, but I'm stuck on %a, I really don't understand what is happening here for example:

printf("%a\n", 3.0); //#=> 0x1.8p+1
printf("%a\n", 3.1); //#=> 0x1.8cccccccccccdp+1
printf("%a\n", 3.2); //#=> 0x1.999999999999ap+1
printf("%a\n", 3.3); //#=> 0x1.a666666666666p+1
printf("%a\n", 3.4); //#=> 0x1.b333333333333p+1
printf("%a\n", 3.5); //#=> 0x1.cp+1
printf("%a\n", 3.6); //#=> 0x1.ccccccccccccdp+1

Of course I read the man which says:

The double argument is rounded and converted to hexadecimal notation in the style[-]0xh.hhhp[+-]d, where the number of digits after the hexadecimal-point character is equal to the precision specification.

But this doesn't really help I don't understand the process that transforms 3.2 to 1.999999999999ap+1

I don't need any code but really more an explanation.

PS: If this isn't the place for this question could you point me to the right place?

EDIT: While @juhist answer works for numbers >= 1.0 it doesn't explain how to get the result for numbers between 0.0 et 1.0:

printf("%a\n", 0.01); //#=> 0x1.47ae147ae147bp-7
printf("%a\n", 0.1);  //#=> 0x1.999999999999ap-4
printf("%a\n", 0.2);  //#=> 0x1.999999999999ap-3
printf("%a\n", 0.3);  //#=> 0x1.3333333333333p-2
printf("%a\n", 0.4);  //#=> 0x1.999999999999ap-2
printf("%a\n", 0.5);  //#=> 0x1p-1
printf("%a\n", 0.6);  //#=> 0x1.3333333333333p-1

Also I would really like a precision on this The "a" near the end occurs due to limited floating point calculation precision concerning the conversion: printf("%a\n", 3.2); //#=> 0x1.999999999999ap+1

EDIT2: Now the last mystery is to explain why in this case:

printf("%a\n", 0.1); //#=> 0x1.999999999999ap-4

The last 9 becomes and a and in this case:

printf("%a\n", 0.3); //#=> 0x1.3333333333333p-2

The last 3 stays a 3?

Victor2748
  • 4,149
  • 13
  • 52
  • 89
ItsASecret
  • 2,589
  • 3
  • 19
  • 32

2 Answers2

4

First you need to know what the representation 0xh.hhhh p±d, mean? Let's understand it by taking an example of hexadecimal constant 0x1.99999ap+1.
The digit 1 before the decimal point is a hex digit and the number of hexadecimal digits after it (99999a) is equal to the precision. 0x is the hex introducer and the p is exponent field. The exponent is a decimal number that indicates the power of 2 by which the significant part is multiplied.

So, when 0x1.99999ap+1 will be multiplied with 21 then it will be converted to 3.2 in decimal. Recall that how 1.55e+1 converted to 15.500000 in decimal. Similar thing is happening here.

Now you need to know the mathematics behind the conversion of 0x1.99999ap+1 to 3.2. This will proceed as follows

1*160 + 9*16-1 + 9*16-2 + 9*16-3 + 9*16-4 + 9*16-5 + 10*16-1

Which is (in decimal) equal to 

 1.60000002384185791015625

You need only up to 1 precision. So, take 1.6 and multiply it with 21. Which will give 3.2.

To go to the reverse of the above process you need to find power of 2 by which the floating point number will be divided to obtain the digit 1 before decimal point. After that use successive multiplications to change the fractional part to hexadecimal fraction. Proceed as follows:

  1. 3.2/21 = 1.6
  2. Take integral part from 1.6 to obtain the hex-digit 1 before decimal point.
  3. Multiply .6 by 16. The the integral part obtained will becomes a numeral in the hexadecimal fraction. Repeat this step with the obtained fractional part to the desired precision (6 is default).
    • .6 * 16 = 9.6 ---> Integral part = 9 Fractional part = .6
    • .6 * 16 = 9.6 ---> Integral part = 9 Fractional part = .6
    • .6 * 16 = 9.6 ---> Integral part = 9 Fractional part = .6
    • .6 * 16 = 9.6 ---> Integral part = 9 Fractional part = .6
    • .6 * 16 = 9.6 ---> Integral part = 9 Fractional part = .6
    • .6 * 16 = 9.6 ---> Integral part = 9 Fractional part = .6

So the hexadecimal fraction will become .999999 Now combine hex indicator 0x, hex-digit before decimal point and the hexadecimal fraction obtained along with exponent field to get the result.

3.210 = 0x1.999999p+116

Similarly you can obtain hexadecimal floating point number for numbers less than 1.0., for example 0.01. In this case to obtain the hex-digit 1 before decimal point you need to divide it with a number which is power of 2. Since 128 (25) after multiplying with 0.01 will give the number whose integral part becomes 1, 128*.01 = 1.28. It means you need to multiply 0.01 by 1/2-5 or you can say you need to divide it by 2-5 to get 1.28. Now apply the steps 2 and 3 stated above.

haccks
  • 104,019
  • 25
  • 176
  • 264
  • Yes but what I was asking was the *opposite* process, I understand this fine. I was looking for the *process* of going from `3.2` to `0x1.999999999999ap+1` – ItsASecret Mar 19 '15 at 13:50
  • @ItsASecret; Is it really difficult to go reverse? – haccks Mar 19 '15 at 13:52
  • That's great thanks ! If you include numbers between 0.0 and 1.0 I'll accept it – ItsASecret Mar 19 '15 at 14:52
  • The algorithm given above is general. You can apply it for numbers between `0.0` and `1.0`. I added an example. – haccks Mar 19 '15 at 15:19
  • @ItsASecret; Other anther answer is also correct and approach is quite same. N o need to unaccept that answer over mine. You can change your mind. :) – haccks Mar 19 '15 at 20:34
  • Haha yours look cleaner, also I have one last question, I'm having trouble with the precision, for example if I want to to do `printf("%.6a\n", 3.2);` it outputs `0x1.99999a` how can I round the `double` to get the last `a` mine outputs `0x1.999999p+1` because I stop after 6 iterations :/ – ItsASecret Mar 19 '15 at 20:38
  • Unfortunately, at the top of my head, there is no way. – haccks Mar 19 '15 at 21:08
  • Thanks anyway I'll keep looking ^_^ – ItsASecret Mar 19 '15 at 21:09
3

This is an easy question to answer.

The obvious explanation is that (1 + 9.0/16 + 9.0/(16*16) + 9.0/(16*16*16) + 9.0/(16*16*16*16) + ...)*2 = 3.2

You can easily verify this by taking the five first terms and write this to a Python interpreter: (1 + 9.0/16 + 9.0/(16*16) + 9.0/(16*16*16) + 9.0/(16*16*16*16))*2

The answer is 3.199981689453125.

Why the 2 at the end, then? Of course, because (1<<1) = 2 and the number after the "p" was +1. If you would have +2, then you would use (1<<2) = 4 instead as the multiplier.

EDIT: Ok, so an opposite algorithm was needed.

First, find the shift amount x for which (3.2/(2^x)) is between 1 and 2. In this case, 3.2/(2^1) = 3.2/2 = 1.6.

Then, output "1." and subtract 1 from the result, giving 0.6

Then, multiply the result by 16 and take the integer part. The product is 9.6. Output is "9".

Then, subtract the output from the result. 9.6 - 9 = 0.6.

Repeat: multiply the result by 16 and take the integer part. The product is 9.6. Output is "9".

Again, subtract the output from the result. 9.6 - 9 = 0.6

Repeat these processes. Ad infinitum, if you want the full expansion, but in practice you would stop the iteration somewhere. At the end, you output "p" and "+1" because the power was +1. The "a" near the end occurs due to limited floating point calculation precision.

Another edit: to fully understand what effects the limited precision is going to have, you can read "What Every Computer Scientist Should Know About Floating-Point Arithmetic", a very famous paper that has an online version e.g. there: http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

An example for the algorithm for the number 0.1: we find that 0.1/(2^(-4)) = 0.1*2^4 = 0.1*16 = 1.6 which is between 1 and 2 so we choose the power -4. So, we output "1." and then calulate (1.6-1)=0.6 and multiply it by 16: 16*0.6 = 9.6. So, we output "9", subtract 9.6 - 9 = 0.6 and multiply again it by 16, giving another "9". And so on. So, the answer is "1.9999999....p-4" given unlimited floating point precision. But, due to limited precision, it appears the last letter is "a". So, the algorithm also works for negative powers but then you have to note that dividing by a negative power is the same as multiplying by a positive power. So, you need to consider negative numbers as well in selecting the power which gives the value between 1 and 2.

juhist
  • 4,210
  • 16
  • 33
  • 1
    Yeah this wasn't what I asked, I asked the opposite *process* how to go from `3.2` to `1.999999999999ap+1` – ItsASecret Mar 19 '15 at 12:20
  • Oh, ok. So you understand the process which transforms 1.99999ap+1 to 3.2 but not the reverse process? I have to think a bit more then to see if I can answer. – juhist Mar 19 '15 at 12:21
  • Yes I see how to go back to `3.2` but not the opposite :/ – ItsASecret Mar 19 '15 at 12:25
  • Now there's the opposite algorithm. Wasn't that hard for me but required some thought. – juhist Mar 19 '15 at 12:29
  • Ok great but still incomplete at the end you say `The "a" near the end occurs due to limited floating point calculation precision` that doesn't tell me how I can know it's going to be an `a` :/ ? I mean because sometimes it seems to round up like a `9` becomes an `a` and sometimes it stays the same like for `3.3` a `6` stays a `6`. – ItsASecret Mar 19 '15 at 12:36
  • Well, the only way you can know it's going to be an "a" is by implementing the algorithm in C code using the double data type. If you have any troubles transforming my example use case into an algorithm, tell where you're having problems and I see if I can edit my answer. If you have infinite precision, it's really 1.99999999....p+1 with an infinite number of 9's. But with a finite precision the last character is "a" in this case. – juhist Mar 19 '15 at 12:39
  • I have the same precision requirement the official `printf` has, so a default one and one that can be passed like this `%.10a` means a precision of 10. Also I don't think I'll have any problem implementing your algorithm as long as everything is explained, so except for the ending `a` everything else is fine. – ItsASecret Mar 19 '15 at 12:41
  • While I don't doubt the paper is fascinating, the level required to understand it is way beyond mine :( I just needed to know in which cases the `9` was promoted to `a` and in which cases it stays a `9`. – ItsASecret Mar 19 '15 at 12:48
  • Also I edited my question to include numbers between 0.0 and 1.0. – ItsASecret Mar 19 '15 at 13:17
  • I edited the answer to include an example for also 0.1. So, you need to consider negative powers as well. Note that 0.1/(2^(-4)) = 0.1*2^4, so dividing by a negative power is the same as multiplying with a positive power. Unfortunately, I don't have a better explanation for why the last character is "a" instead of "9" other than "run the algorithm and see what it prints". – juhist Mar 19 '15 at 13:28
  • Ok great thank you very much, I'm going to wait a little to see if someone can explain it and then I'll mark your answer as accepted :) – ItsASecret Mar 19 '15 at 13:29