[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

Thanks, Victor.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

> I wait for the following build to close this issue.
> http://www.python.org/dev/buildbot/all/builders/x86%20Tiger%203.x/builds/2507

Oh, it's the wrong build. The correct build is:
http://www.python.org/dev/buildbot/all/builders/x86%20Tiger%203.x/builds/2508

And it passed so I close this issue.

--
resolution:  -> fixed
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

> New changeset 34871c3072c9 by Victor Stinner in branch 'default':
> Issue #11888: skip some log2 tests on Mac OS X Tiger

Oh... I realized that the test doesn't fail on Mac OS X Tiger PPC, only on Mac 
OS X Tiger x86. But I am too lazy to patch the test. Or should I do it?

I wait for the following build to close this issue.
http://www.python.org/dev/buildbot/all/builders/x86%20Tiger%203.x/builds/2507

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Roundup Robot]

Roundup Robot  added the comment:

New changeset 34871c3072c9 by Victor Stinner in branch 'default':
Issue #11888: skip some log2 tests on Mac OS X Tiger
http://hg.python.org/cpython/rev/34871c3072c9

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

Victor, what do you think about simply #undefining HAVE_LOG2 on Tiger (e.g. in 
pyport.h), so that the fallback log2 version is used there instead of the 
system version?

Does anyone know the appropriate preprocessor check for OS X <= 10.4?  I can 
get as far as "#ifdef __APPLE__", but don't know how to check for specific 
versions of OS X.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

Thanks, Roumen.  Fixed.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Roundup Robot]

Roundup Robot  added the comment:

New changeset d3f9895e2e19 by Mark Dickinson in branch 'default':
Issue #11888: remove duplicate check for log2 in configure.in.
http://hg.python.org/cpython/rev/d3f9895e2e19

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Roumen Petrov]

Roumen Petrov  added the comment:

Why configure script check two times for log2 function ?

--
nosy: +rpetrov

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

Grr.  Got the issue number wrong in the commit message;  see msg135584.


New changeset 1f23d63b578c by Mark Dickinson in branch 'default':
Issue #11188: In log2 tests, create powers of 2 using ldexp(1, n) instead of 
the less reliable 2.0**n.
http://hg.python.org/cpython/rev/1f23d63b578c

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

Okay, thanks.  We should still be using ldexp rather than 2.0**... in the 
tests, though;  I've fixed this, and also fixed the incorrect (too small) range 
for those tests, so that all representable powers of 2 are now covered.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

> we should check that it's not pow that's at fault here

Some tests on Mac OS X Tiger:

>>> (2.0 ** -255).hex()
'0x1.0p-255'

=> pow is correct

>>> import ctypes; import ctypes.util, math
>>> libc = ctypes.cdll.LoadLibrary(ctypes.util.find_library('c'))
>>> clog2=libc.log2
>>> clog2.restype=ctypes.c_double
>>> clog2.argtypes=(ctypes.c_double,)
>>> clog2(2.0**-255)
-254.97
>>> math.log(2.0**-255) / math.log(2.0)
-255.0

>>> math.log(2.0**-255)
-176.75253104278605
>>> math.log(2.0**-255).hex()
'-0x1.61814bbfb3fb5p+7'
>>> math.log(2.0)
0.6931471805599453
>>> math.log(2.0).hex()
'0x1.62e42fefa39efp-1'

>>> clog2(2.0**-255).hex()
'-0x1.fdfffp+7'
>>> (math.log(2.0**-255) / math.log(2.0)).hex()
'-0x1.fe000p+7'

clog2() is wrong for 2^-255.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

One other thought:  we should check that it's not pow that's at fault here, 
rather than log2.  The test uses math.log2(2.0**n).  It would probably be 
better off using math.log2(ldexp(1.0, n)), or similar:  the libm pow operation 
is also notorious for inaccuracies (due to poor implementations or otherwise) 
on various platforms.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

> You know what? Mac OS X log2 is less accurate than Python log2!

That doesn't surprise me much.  Though it's probably still true that log2 from 
OS X is more accurate than our log2 for some other values.  It's just that 
getting the answer wrong for a power of 2 is a 'high-visibility' error.

Testing log2 sounds long-winded and error-prone.  I'd suggest just marking that 
test as an expected failure on Tiger.  BTW, I don't see any such failure on 
Snow Leopard.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

Issue #11888: Use system log2() when available
http://hg.python.org/cpython/rev/565f43f6bed4

"I expect the system libc to use more accurate functions than Python."

You know what? Mac OS X log2 is less accurate than Python log2! A log2 test 
failed on "x86 Tiger 3.x":

http://www.python.org/dev/buildbot/all/builders/x86%20Tiger%203.x/builds/2488
==
FAIL: testLog2 (test.test_math.MathTests)
--
Traceback (most recent call last):
  File "/Users/db3l/buildarea/3.x.bolen-tiger/build/Lib/test/test_math.py", 
line 658, in testLog2
self.assertEqual(actual, expected)
AssertionError: Lists differ: [-324.0, -323.0, -322.0, -321 != [-324.0, 
-323.0, -322.0, -321

First differing element 69:
-254.97
-255.0
--

Should I revert my patch or should we test the system log2 in configure to 
check if it is as accurate or more accurate than Mark's algorithm?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Roundup Robot]

Roundup Robot  added the comment:

New changeset 565f43f6bed4 by Victor Stinner in branch 'default':
Issue #11888: Use system log2() when available
http://hg.python.org/cpython/rev/565f43f6bed4

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

> we have to wait 12 hours or maybe one day to wait for all buildbots

Oh, it's faster than expected: test_math passed on FreeBSD 6.4 3.x buildbot. I 
was waiting for this one because it's an old OS and many tests fail on this 
buildbot (because it's old but also slow). So test_math passed on all 
buildbots. Let's try the system log2 :-)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

> Thanks, Victor.  You caught me by surprise a bit

Oh, I thought that the patch was ready to be commited.

> I had some more minor changes to that patch pending,
> so I've committed those separately.

You should add "Issue #11888: " prefix to your commit messages so a bot 
automatically add comments for the new commits to this issue.

> "Fix cut-and-paste typo in comment: log10 -> log2."

Oh, I didn't notice it, but Terry Reedy

> "Fix nonunique test ids in math_testcases.txt."

Oh, I didn't notice it: why do we need explicit identifiers? Can't we use the 
line number or something like that? What happens if two tests have the same 
identifier? Is the first test skipped?

> Any news from the buildbots?

Yes, most of them are happy. Some of them are busy (don't have test log2() 
yet), others are unhappy but not because of log2(). Said differently: log2 
tests pass on most buildbots, but we have to wait 12 hours or maybe one day to 
wait for all buildbots.

If the test pass on all buildbots, I will commit issue11888-part2.patch to use 
the system log2 function.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

Thanks, Victor.  You caught me by surprise a bit:  I had some more minor 
changes to that patch pending, so I've committed those separately.

Any news from the buildbots?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Roundup Robot]

Roundup Robot  added the comment:

New changeset 6d1cbfcee45a by Victor Stinner in branch 'default':
Issue #11888: Add log2 function to math module. Patch written by Mark
http://hg.python.org/cpython/rev/6d1cbfcee45a

--
nosy: +python-dev

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

By the way, issue11888.patch is just fine: you can commit it. I like your frexp 
"trick" to improve the accuracy.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

Changes by STINNER Victor :


Removed file: http://bugs.python.org/file21897/issue11888-2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

(Oh, I hit the wrong keyboard shortcut and sent my email too fast)

You can commit issue11888.patch first if you would like to test it.

In this case, here is a patch to use system log2(), patch to apply *after* 
issue11888.patch. It only uses log2() if x > 0.0.

--
Added file: http://bugs.python.org/file21918/issue11888-part2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

> Thanks, Victor.  I suspect we're going to need to be a bit more
> careful, though:  when the extra tests were added for math.log, it
> turned out that it had all sorts of strange special-case behaviour on
> various platforms.
> 
> So I suspect that even on platforms that have log2 natively, it'll be
> necessary to factor out special cases and deal with those first, only
> passing positive finite floats onto the system log2.  Take a look at
> m_log and the comment directly above it to see how that works.

Oh, I see:

/*  
Various platforms (Solaris, OpenBSD) do nonstandard things for
log(0),  
log(-ve), log(NaN).  Here are wrappers for log and log10 that deal
with 
special values directly, passing positive non-special values through
to 
the system
log/log10.   
 */  

> I'd also like to check in the non-system version first, just to give
> it a thorough test on the buildbots, before adding in the version that
> uses the system log2 when available.

Yes, we can use log2() only for the "x > 0.0" case. My secret plan was
to check system log2() using the buildbots. But if we know that system
log() only works correctly with strictly positive numbers, it's faster
to directly only use system log2() for x > 0.0.

Updated patch (version 3) implements that.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

Thanks, Victor.  I suspect we're going to need to be a bit more careful, 
though:  when the extra tests were added for math.log, it turned out that it 
had all sorts of strange special-case behaviour on various platforms.

So I suspect that even on platforms that have log2 natively, it'll be necessary 
to factor out special cases and deal with those first, only passing positive 
finite floats onto the system log2.  Take a look at m_log and the comment 
directly above it to see how that works.

I'd also like to check in the non-system version first, just to give it a 
thorough test on the buildbots, before adding in the version that uses the 
system log2 when available.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

Updated patch to use the system log2() if it is available. The test pass with 
the system log2() on Linux (Debian Sid, eglibc 2.11.2).

--
Added file: http://bugs.python.org/file21897/issue11888-2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Wow Mark, that is really nice work.  Thanks.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

Here's a patch implementing log2.  Still to do:  use the system log2 where 
available.

--
keywords: +patch
Added file: http://bugs.python.org/file21861/issue11888.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

Oh... math.log() has an optional second argument: base. math.log(x, 2). But it 
is equivalent as math.log(x) / math.log(2) in Python. math.log(x, 2) is 
implemented as:
  num=math.log(x)
  den=math.log(2)
  return num / den
where num and den are Python floats (64 bits).

So we don't benefit from 80 bits float used internally in x87.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

> Can't we simply use (approximation to 1/log(2)) * log(x)?
> Is it worse than reimplementing it using log(x)/log(2) in Python?

Hum. With a x86 and the right compiler optimization level, log(x)/log(2) in C 
can be more accurate than log(x)/log(2) in Python, because the FPU works with 
80 bits float internally, and the result is only "truncated" to 64 bits float 
at the end. In Python, the result is truncated to 64 bits on each Python 
instruction.

I don't know if it should be called a feature or a bug. In PHP world, it would 
be called a bug :-D http://bugs.php.net/bug.php?id=53632

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

> The main issue is that we'd have to provide (and maintain) our own
> implementation of log2 for Windows (and other OSs that don't have all
> the C99 support.  Solaris?)

Can't we simply use (approximation to 1/log(2)) * log(x)? Is it worse than 
reimplementing it using log(x)/log(2) in Python?

> That implementation should, ideally: ...

Because some platforms are less accurate, you prefer to not provide a more 
accurate function when log2() is available? Can't we start with something 
simple and improve it later?

It can be documented than the Python log2 function may be the same than 
log(x)/log(2) if the platform/CPU doesn't provide a C log2 function.

--

"... And indeed, on Windows ...

>>> numpy.log2(8.0)
2.9996"

Oh. Python is better on Linux:

Python 2.6.6 (r266:84292, Dec 26 2010, 22:31:48) 
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> math.log(8) / math.log(2)
3.0

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

> it may be worth looking at what numpy does here.

... or it may not.  NumPy just uses (approximation to 1/log(2)) * log(x) when 
log2 doesn't already exist.  And indeed, on Windows:

Python 2.7.1 |EPD 7.0-2 (64-bit)| (r271:86832, Dec  2 2010, 10:23:25) [MSC 
v.1500 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import numpy
>>> numpy.log2(8.0)
2.9996

I think we should be able to do better than this. :-)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

Rather than reinventing the wheel, it may be worth looking at what numpy does 
here.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

> We can provide log2() only if the C library has this function.

Big -1 from me:  I'd hate to see working Python scripts written on Unix fail on 
Windows because of a missing log2.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[STINNER Victor]

STINNER Victor  added the comment:

> The main issue is that we'd have to provide (and maintain) our own
> implementation of log2 for Windows (and other OSs that don't have all
> the C99 support.  Solaris?)

No, we don't have to. Python has already a lot of optional functions, see for 
example the os module. We can provide log2() only if the C library has this 
function.

--
nosy: +haypo

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Mark Dickinson]

Mark Dickinson  added the comment:

See also issue 3724.

I'm -0 on this:  between log(x, 2) and int.bit_length, there's not much need 
for log2.  log(x, 2) should be plenty accurate enough for most numerical needs; 
 the exception is when you're taking log base 2 of an integer and need a 
guarantee of exact results for powers of 2, and int.bit_length generally solves 
that problem.

The main issue is that we'd have to provide (and maintain) our own 
implementation of log2 for Windows (and other OSs that don't have all the C99 
support.  Solaris?)  That implementation should, ideally:

 - provide exact values for powers of 2, and
 - be monotonic.

and that's not trivial.  As Raymond points out, on x86 / x64 we might be able 
to use inline assembly directly;  that would probably cover us for Windows.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Jesús Cea Avión]

Changes by Jesús Cea Avión :


--
nosy: +jcea

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue11888] Add C99's log2() function to the math library

[Raymond Hettinger]

New submission from Raymond Hettinger :

The three most popular logarithm bases are 10, e, and 2.  The math library has 
direct function calls for the first two but not the latter which is important 
in informatics.

Since a direct call can use a custom algorithm or native hardware support (such 
as the FLDLN2 fpu instruction), it provides better speed and accuracy than our 
existing math.log(x, 2) option.

--
assignee: mark.dickinson
messages: 134159
nosy: mark.dickinson, rhettinger
priority: normal
severity: normal
status: open
title: Add C99's log2() function to the math library
type: feature request
versions: Python 3.3

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com