digitalmars.D.learn - log2 buggy or is a real thing?

• Jonathan M Davis (31/31) Apr 04 2012 This progam:
• bearophile (36/75) Apr 04 2012 What is the problem you are perceiving?
• Don Clugston (7/82) Apr 04 2012 I don't think so. For 80-bit reals, every long can be represented
• Timon Gehr (4/8) Apr 04 2012 ?
• Don Clugston (5/15) Apr 04 2012 Ah, you're right. I forgot about the implicit bit. 80 bit reals are
• bearophile (12/12) Apr 04 2012 Do you know why is this program:
• Timon Gehr (2/14) Apr 04 2012 Works correctly here. (x64 linux)
• Don Clugston (2/14) Apr 04 2012 Poor float->decimal conversion in the C library ftoa() function.
```This progam:

import std.math;
import std.stdio;
import std.typetuple;

ulong log2(ulong n)
{
return n == 1 ? 0
: 1 + log2(n / 2);
}

void print(ulong value)
{
writefln("%s: %s %s", value, log2(value), std.math.log2(value));
}

void main()
{
foreach(T; TypeTuple!(byte, ubyte, short, ushort, int, uint, long, ulong))
print(T.max);
}

prints out

127: 6 6.98868
255: 7 7.99435
32767: 14 15
65535: 15 16
2147483647: 30 31
4294967295: 31 32
9223372036854775807: 62 63
18446744073709551615: 63 64

So, the question is: Is std.math.log2 buggy, or is it just an issue with the
fact that std.math.log2 is using reals, or am I completely misunderstanding
something here?

- Jonathan M Davis
```
Apr 04 2012
```Jonathan M Davis:

This progam:

import std.math;
import std.stdio;
import std.typetuple;

ulong log2(ulong n)
{
return n == 1 ? 0
: 1 + log2(n / 2);
}

void print(ulong value)
{
writefln("%s: %s %s", value, log2(value), std.math.log2(value));
}

void main()
{
foreach(T; TypeTuple!(byte, ubyte, short, ushort, int, uint, long, ulong))
print(T.max);
}

prints out

127: 6 6.98868
255: 7 7.99435
32767: 14 15
65535: 15 16
2147483647: 30 31
4294967295: 31 32
9223372036854775807: 62 63
18446744073709551615: 63 64

So, the question is: Is std.math.log2 buggy, or is it just an issue with the
fact that std.math.log2 is using reals, or am I completely misunderstanding
something here?

What is the problem you are perceiving?

The values you see are badly rounded, this is why I said that the Python
floating point printing function is better than the D one :-)

I print the third result with more decimal digits using %1.20f, to avoid that

import std.stdio, std.math, std.typetuple;

ulong mlog2(in ulong n) pure nothrow {
return (n == 1) ? 0 : (1 + mlog2(n / 2));
}

void print(in ulong x) {
writefln("%s: %s %1.20f", x, mlog2(x), std.math.log2(x));
}

void main() {
foreach (T; TypeTuple!(byte, ubyte, short, ushort, int, uint, long, ulong))
print(T.max);
print(9223372036854775808UL);
real r = 9223372036854775808UL;
writefln("%1.20f", r);
}

The output is:

127: 6 6.98868468677216585300
255: 7 7.99435343685885793770
32767: 14 14.99995597176955822200
65535: 15 15.99997798605273604400
2147483647: 30 30.99999999932819277100
4294967295: 31 31.99999999966409638400
9223372036854775807: 62 63.00000000000000000100
18446744073709551615: 63 64.00000000000000000000
9223372036854775808: 63 63.00000000000000000100
9223372036854775807.80000000000000000000

And it seems essentially correct, the only significant (but very little)
problem I am seeing is
log2(9223372036854775807) that returns a value > 63, while of course in truth
it's strictly less than 63 (found with Wolfram Alpha):
62.999999999999999999843582690243412222355489972678233
The cause of that small error is the limited integer representation precision
of reals.

In Python there is a routine to compute precisely the logarithm of large
integer numbers. It will be useful to have in D too, for BigInts too.

Bye,
bearophile
```
Apr 04 2012
```On 04/04/12 13:40, bearophile wrote:
Jonathan M Davis:

This progam:

import std.math;
import std.stdio;
import std.typetuple;

ulong log2(ulong n)
{
return n == 1 ? 0
: 1 + log2(n / 2);
}

void print(ulong value)
{
writefln("%s: %s %s", value, log2(value), std.math.log2(value));
}

void main()
{
foreach(T; TypeTuple!(byte, ubyte, short, ushort, int, uint, long, ulong))
print(T.max);
}

prints out

127: 6 6.98868
255: 7 7.99435
32767: 14 15
65535: 15 16
2147483647: 30 31
4294967295: 31 32
9223372036854775807: 62 63
18446744073709551615: 63 64

So, the question is: Is std.math.log2 buggy, or is it just an issue with the
fact that std.math.log2 is using reals, or am I completely misunderstanding
something here?

What is the problem you are perceiving?

The values you see are badly rounded, this is why I said that the Python
floating point printing function is better than the D one :-)

I print the third result with more decimal digits using %1.20f, to avoid that

import std.stdio, std.math, std.typetuple;

ulong mlog2(in ulong n) pure nothrow {
return (n == 1) ? 0 : (1 + mlog2(n / 2));
}

void print(in ulong x) {
writefln("%s: %s %1.20f", x, mlog2(x), std.math.log2(x));
}

void main() {
foreach (T; TypeTuple!(byte, ubyte, short, ushort, int, uint, long,
ulong))
print(T.max);
print(9223372036854775808UL);
real r = 9223372036854775808UL;
writefln("%1.20f", r);
}

The output is:

127: 6 6.98868468677216585300
255: 7 7.99435343685885793770
32767: 14 14.99995597176955822200
65535: 15 15.99997798605273604400
2147483647: 30 30.99999999932819277100
4294967295: 31 31.99999999966409638400
9223372036854775807: 62 63.00000000000000000100
18446744073709551615: 63 64.00000000000000000000
9223372036854775808: 63 63.00000000000000000100
9223372036854775807.80000000000000000000

And it seems essentially correct, the only significant (but very little)
problem I am seeing is
log2(9223372036854775807) that returns a value>  63, while of course in truth
it's strictly less than 63 (found with Wolfram Alpha):
62.999999999999999999843582690243412222355489972678233
The cause of that small error is the limited integer representation precision
of reals.

I don't think so. For 80-bit reals, every long can be represented
exactly in an 80 bit real, as can every ulong from 0 up to and including
ulong.max - 1. The only non-representable built-in integer is ulong.max,
which (depending on rounding mode) gets rounded up to ulong.max+1.

The decimal floating point output for DMC, which DMD uses, is not very
accurate. I suspect the value is actually <= 63.

In Python there is a routine to compute precisely the logarithm of large
integer numbers. It will be useful to have in D too, for BigInts too.

Bye,
bearophile

```
Apr 04 2012
```On 04/04/2012 05:15 PM, Don Clugston wrote:
I don't think so. For 80-bit reals, every long can be represented
exactly in an 80 bit real, as can every ulong from 0 up to and including
ulong.max - 1. The only non-representable built-in integer is ulong.max,
which (depending on rounding mode) gets rounded up to ulong.max+1.

?

assert(0xffffffffffffffffp0L == ulong.max);
assert(0xfffffffffffffffep0L == ulong.max-1);
```
Apr 04 2012
```On 04/04/12 18:53, Timon Gehr wrote:
On 04/04/2012 05:15 PM, Don Clugston wrote:
I don't think so. For 80-bit reals, every long can be represented
exactly in an 80 bit real, as can every ulong from 0 up to and including
ulong.max - 1. The only non-representable built-in integer is ulong.max,
which (depending on rounding mode) gets rounded up to ulong.max+1.

?

assert(0xffffffffffffffffp0L == ulong.max);
assert(0xfffffffffffffffep0L == ulong.max-1);

Ah, you're right. I forgot about the implicit bit. 80 bit reals are
equivalent to 65bit signed integers.

It's ulong.max+2 which is the smallest unrepresentable integer.

Conclusion: you cannot blame ANYTHING on the limited precision of reals.
```
Apr 04 2012
```Do you know why is this program:

import std.stdio;
void main() {
real r = 9223372036854775808UL;
writefln("%1.19f", r);
}

Printing:
9223372036854775807.8000000000000000000

9223372036854775808.0000000000000000000

Bye,
bearophile
```
Apr 04 2012
```On 04/04/2012 01:46 PM, bearophile wrote:
Do you know why is this program:

import std.stdio;
void main() {
real r = 9223372036854775808UL;
writefln("%1.19f", r);
}

Printing:
9223372036854775807.8000000000000000000

9223372036854775808.0000000000000000000

Bye,
bearophile

Works correctly here. (x64 linux)
```
Apr 04 2012    Don Clugston <dac nospam.com> writes:
```On 04/04/12 13:46, bearophile wrote:
Do you know why is this program:

import std.stdio;
void main() {
real r = 9223372036854775808UL;
writefln("%1.19f", r);
}

Printing:
9223372036854775807.8000000000000000000