I have a couple of questions for the number crunchers out there:
Does "pow(x,2)" simply square x, or does it first compute logarithms
(as would be necessary if the exponent were not an integer)?
Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some
other (perhaps less efficient) algorithm based on logarithms?
Thanks,
Russ 11 4433
Russ wrote: I have a couple of questions for the number crunchers out there:
Does "pow(x,2)" simply square x, or does it first compute logarithms (as would be necessary if the exponent were not an integer)?
Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some other (perhaps less efficient) algorithm based on logarithms?
you can try and timeit 111**111
107362012888474 225801214565046 695501959850723 994224804804775 911175625076195 783347022491226 170093634621466 103743092986967 777786330067310 159463303558666 910091026017785 587295539622142 057315437069730 229375357546494 103400699864397 711L timeit.Timer("p ow(111,111)").t imeit()
40.888447046279 907 timeit.Timer("1 11**111").timei t()
39.732122898101 807 timeit.Timer("1 11**0.5").timei t()
2.0990891456604 004 timeit.Timer("p ow(111,0.5)").t imeit()
4.1776390075683 594 timeit.Timer("1 11**0.3").timei t()
2.3824679851531 982 timeit.Timer("p ow(111,0.3)").t imeit()
4.2945041656494 141
interesting result
seems that ** computates faster
I not shure which algorithm,but I am assumeing that all Python does,is
to call the underlying C pow() function.
Sam
Schüle Daniel <uv**@rz.unikarlsruhe.de> writes: >>> timeit.Timer("1 11**0.3").timei t() 2.3824679851531 982 >>> timeit.Timer("p ow(111,0.3)").t imeit()
4.2945041656494 141
interesting result seems that ** computates faster
Maybe "111**0.3" parses faster than pow(111,0.3), if timeit uses eval.
Also, pow() may incur more subroutine call overheadbetter check
the bytecode for both versions.
Russ wrote: I have a couple of questions for the number crunchers out there:
Sure, but the answers depend on the underlying Python implementation.
And if we're talking CPython, they also depend on the underlying C
implementation of libm (i.e., math.h).
Does "pow(x,2)" simply square x, or does it first compute logarithms (as would be necessary if the exponent were not an integer)?
The former, using binary exponentiation (quite fast), assuming x is an
int or long.
If x is a float, Python coerces the 2 to 2.0, and CPython's float_pow()
function is called. This function calls libm's pow(), which in turn
uses logarithms.
Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some other (perhaps less efficient) algorithm based on logarithms?
The latter, and that algorithm is libm's pow(). Except for a few
special cases that Python handles, all floating point exponentation is
left to libm. Checking to see if the exponent is 0.5 is not one of
those special cases.
If you're curious, download the Python source, open up
Objects/floatobject.c, and check out float_pow(). The binary
exponentation algorithms are in Objects/intobject:int_p ow() and
Objects/longobject:long _pow().
The 0.5 special check (and any other special case optimizations) could,
in theory, be performed in the platform's libm. I'm not familiar
enough with any libm implementations to comment on whether this is ever
done, or if it's even worth doing... though I suspect that the 0.5 case
is not.
Hope that helps,
Ben
Ben Cartwright wrote: Russ wrote:
Does "pow(x,2)" simply square x, or does it first compute logarithms (as would be necessary if the exponent were not an integer)?
The former, using binary exponentiation (quite fast), assuming x is an int or long.
If x is a float, Python coerces the 2 to 2.0, and CPython's float_pow() function is called. This function calls libm's pow(), which in turn uses logarithms.
I just did a little time test (which I should have done *before* my
original post!), and 2.0**2 seems to be about twice as fast as
pow(2.0,2). That seems consistent with your claim above.
I'm a bit surprised that pow() would use logarithms even if the
exponent is an integer. I suppose that just checking for an integer
exponent could blow away the gain that would be achieved by avoiding
logarithms. On the other hand, I would think that using logarithms
could introduce a tiny error (e.g., pow(2.0,2) = 3.9999999996 < made
up result) that wouldn't occur with multiplication. Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some other (perhaps less efficient) algorithm based on logarithms?
The latter, and that algorithm is libm's pow(). Except for a few special cases that Python handles, all floating point exponentation is left to libm. Checking to see if the exponent is 0.5 is not one of those special cases.
I just did another little time test comparing 2.0**0.5 with sqrt(2.0).
Surprisingly, 2.0**0.5 seems to take around a third less time.
None of these differences are really significant unless one is doing
superheavyduty number crunching, of course, but I was just curious.
Thanks for the information.
Russ wrote: Ben Cartwright wrote: Russ wrote: Does "pow(x,2)" simply square x, or does it first compute logarithms (as would be necessary if the exponent were not an integer)?
The former, using binary exponentiation (quite fast), assuming x is an int or long.
If x is a float, Python coerces the 2 to 2.0, and CPython's float_pow() function is called. This function calls libm's pow(), which in turn uses logarithms.
I just did a little time test (which I should have done *before* my original post!), and 2.0**2 seems to be about twice as fast as pow(2.0,2). That seems consistent with your claim above.
Actually, the fact that x**y is faster than pow(x, y) has nothing do to
with the int vs. float issue. It's actually due to do the way Python
parses operators versus builtin functions. Paul Rubin hit the nail on
the head when he suggested you check the bytecode: import dis dis.dis(lambda x, y: x**y)
1 0 LOAD_FAST 0 (x)
3 LOAD_FAST 1 (y)
6 BINARY_POWER
7 RETURN_VALUE dis.dis(lambda x, y: pow(x,y))
1 0 LOAD_GLOBAL 0 (pow)
3 LOAD_FAST 0 (x)
6 LOAD_FAST 1 (y)
9 CALL_FUNCTION 2
12 RETURN_VALUE
LOAD_GLOBAL + CALL_FUNCTION is more expensive than LOAD_FAST,
especially when you're doing it a million times (which, coincidentally,
timeit does).
Anyway, if you want to see the int vs. float issue in action, try this:
from timeit import Timer Timer('2**2').t imeit()
0.1268101158232 1844 Timer('2.0**2.0 ').timeit()
0.3333601174343 8121 Timer('2.0**2') .timeit()
0.3668183555611 2219 Timer('2**2.0') .timeit()
0.3794981837060 0497
As you can see, the int version is much faster than the float version.
The last two cases, which also use the float version, have an
additional performance hit due to type coercion. The relative speed
differences are similar when using pow():
Timer('pow(2, 2)').timeit()
0.3300096886915 7532 Timer('pow(2.0, 2.0)').timeit()
0.5035636218470 9269 Timer('pow(2.0, 2)').timeit()
0.5511293818585 7274 Timer('pow(2, 2.0)').timeit()
0.5519881960581 1877
I'm a bit surprised that pow() would use logarithms even if the exponent is an integer. I suppose that just checking for an integer exponent could blow away the gain that would be achieved by avoiding logarithms. On the other hand, I would think that using logarithms could introduce a tiny error (e.g., pow(2.0,2) = 3.9999999996 < made up result) that wouldn't occur with multiplication.
These are good questions to ask an expert in floating point arithmetic.
Which I'm not. :)
Does "x**0.5" use the same algorithm as "sqrt(x)", or does it use some other (perhaps less efficient) algorithm based on logarithms?
The latter, and that algorithm is libm's pow(). Except for a few special cases that Python handles, all floating point exponentation is left to libm. Checking to see if the exponent is 0.5 is not one of those special cases.
I just did another little time test comparing 2.0**0.5 with sqrt(2.0). Surprisingly, 2.0**0.5 seems to take around a third less time.
Again, this is because of the operator vs. function lookup issue.
pow(2.0, 0.5) vs. sqrt(2.0) is a better comparison: from timeit import Timer Timer('pow(2.0, 0.5)').timeit()
0.5170143710281 5362 Timer('sqrt(2.0 )', 'from math import sqrt').timeit()
0.4664909672223 9847
None of these differences are really significant unless one is doing superheavyduty number crunching, of course, but I was just curious. Thanks for the information.
Welcome. :)
Ben
On Wed, 20060315 at 18:46 0800, Ben Cartwright wrote: Anyway, if you want to see the int vs. float issue in action, try this:
>>> from timeit import Timer >>> Timer('2**2').t imeit() 0.1268101158232 1844 >>> Timer('2.0**2.0 ').timeit() 0.3333601174343 8121 >>> Timer('2.0**2') .timeit() 0.3668183555611 2219 >>> Timer('2**2.0') .timeit() 0.3794981837060 0497
As you can see, the int version is much faster than the float version.
I have a counterexample. In the original timeit example, 111**111 was
used. When I run that timeit.Timer("p ow(111,111)").t imeit()
10.968398094177 246 timeit.Timer("1 11**111").timei t()
10.040078878402 71 timeit.Timer("1 11.**111.").tim eit()
0.3657629489898 6816
The pow and ** on integers take 10 seconds, but the float ** takes only
0.36 seconds. (The pow with floats takes ~ 0.7 seconds). Clearly
typecasting to floats is coming in here somewhere. (Python 2.4.1 on
Linux FC4.)
Mike
Mike Ressler wrote: timeit.Timer("p ow(111,111)").t imeit() 10.968398094177 246 timeit.Timer("1 11**111").timei t() 10.040078878402 71 timeit.Timer("1 11.**111.").tim eit() 0.3657629489898 6816
The pow and ** on integers take 10 seconds, but the float ** takes only 0.36 seconds. (The pow with floats takes ~ 0.7 seconds). Clearly typecasting to floats is coming in here somewhere. (Python 2.4.1 on Linux FC4.)
No, there is not floating point math going on when the operands to **
are both int or long. If there were, the following two commands would
have identical output: 111**111
107362012888474 225801214565046 695501959850723 994224804804775 911
175625076195783 347022491226170 093634621466103 743092986967777 786
330067310159463 303558666910091 026017785587295 539622142057315 437
069730229375357 546494103400699 864397711L int(111.0**111. 0)
107362012888474 224720018046104 893130890742038 145054486592605 938
348914231670972 887594279283213 585412743799339 280552157756096 410
839752020853099 983680499334815 422669184408961 411319810030383 904
886446681757296 875373689157536 249282560L
The first result is accurate. Work it out by hand if you don't believe
me. ;) The second suffers from inaccuracies due to floating point's
limited precision.
Of course, getting exact results with huge numbers isn't cheap,
computationally . Because there's no type in C to represent arbitrarily
huge numbers, Python implements its own, called "long". There's a fair
amount of memory allocation, bit shifting, and other monkey business
going on behind the scenes in longobject.c.
Whenever possible, Python uses C's builtin signed long int type (known
simply as "int" on the Python side, and implemented in intobject.c).
On my platform, C's signed long int is 32 bits, so values range from
2147483648 to 2147483647. I.e., (2**31) to (2**31)1.
As long as your exponentiation result is in this range, Python uses
int_pow(). When it overflows, long_pow() takes over. Both functions
use the binary exponentiation algorithm, but long_pow() is naturally
slower:
from timeit import Timer Timer('2**28'). timeit()
0.2457203204382 9495 Timer('2**29'). timeit()
0.2551164279193 4719 Timer('2**30'). timeit()
0.2774678297917 0348 Timer('2**31'). timeit() # overflow: 2**31 > 2147483647
2.8205724462504 804 Timer('2**32'). timeit()
2.2251812151589 547 Timer('2**33'). timeit()
2.4067177773399 635
Floating point is a whole 'nother ball game:
Timer('2.0**30. 0').timeit()
0.3326630196384 0306 Timer('2.0**31. 0').timeit() # no threshold here!
0.3343744676963 0697
Ben
"Mike Ressler" <mi**********@a lum.mit.edu> wrote in message
news:11******** **************@ dhcp78140229.jpl.nasa.go v... I have a counterexample. In the original timeit example, 111**111 was used. When I run that
timeit.Timer("p ow(111,111)").t imeit() 10.968398094177 246 timeit.Timer("1 11**111").timei t() 10.040078878402 71 timeit.Timer("1 11.**111.").tim eit()
0.3657629489898 6816
The pow and ** on integers take 10 seconds, but the float ** takes only 0.36 seconds. (The pow with floats takes ~ 0.7 seconds). Clearly typecasting to floats is coming in here somewhere. (Python 2.4.1 on Linux FC4.)
For floats, f**g == exp(log(f**g)) == exp(g*log(f)) (with maybe further
algebraic manipulation, depending on the implementation) . The time for
this should only be mildly dependent on the magnitudes of f and g.
The time for i**j, on the other hand, grows at least as fast as log(j). So
I should expect comparisons to depend on magnitudes, as you discovered.
Terry Jan Reedy This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics 
by: Aaron Gallimore 
last post by:
Hi,
Pretty simple one I think...Is there a "power of" or squared function in
C++. This is what i'm trying to achieve.
(arrayarray)*2
this doesnt work with minus numbers so i need a square or power function.
also.. Is there a "sum of" function. Ultimately i'm trying to do a euclidean

by: M Welinder 
last post by:
The title more or less says it all: in C99, is the value of
INT_MIN % 1
well defined (when performed as signed integers) under the assumption of
twocomplement representation.
Note, that this is not the usual negativevaluesand% question  the problem
here is that the corresponding signed division, INT_MIN / 1, overflows. Thus
I don't see what use a%b = a(a/b)*b can be here.

by: Dave win 
last post by:
howdy....
plz take a look at the following codes, and tell me the reason.
1 #define swap(a,b) a=a^b;b=b^a;a=a^b
2
3 int main(void){
4 register int a=4;
5 register int b=5;
6 swap(a,b);
7

by: Bjorn Jensen 
last post by:
Hi!
An beginner question:
Pleas help me with this (:
Error (the arrow points on the s in sqrt)
=====
tal.java:6: cannot find symbol
symbol : method sqrt(int)
location: class tal
System.out.println(i + ": " + sqrt(4));

by: Curten 
last post by:
Hi,
When I run a program I have made, i get this error message sometimes:
"Application error:The instruction at '...' referenced memory at '...'. Memory could not be "read"..."
Are there any common mistakes that cause this problem?
Before i get the message above i get this in the command window:
"pow: OVERFLOW error". I suppose these error messages are connected, but how? What causes pow: OVERFLOW error?
 
by: Camellia 
last post by:
hi all,
I wrote a "table of powers" program and made the 5th power the highest,
but when I tried to run the program I found a problem. Here's the
output:
Integer Square power 3rd power 4th power 5th
    
1 1 1 1 1

by: Alexandre Proulx 
last post by:
I am trying to find 2 at the power of 601, but my calculator doesn't have a large enough screen, so I decided to make a program for my computer to do this, but when I get to a high number the computer only prints : 1.#INF00. Is there any way to do it? My code is the fallowing:
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
float a;
float x;
float y;

by: tarlino 
last post by:
Hi! I'm play with the sound generation (c++ and directX).
Now I would like to manage same filter on my sample. But now I must to
convert my audio buffer "BYTE" (from DirectX) to an arry of "short" and
viceversa.
I found this source:
**************************************************************
double dPowI = ceil( log10( (double)iLen / ( ((double)wBitsPerSample / 8 )
+ wChannels  1 ) ) / log10( 2.0 ) );
int iNearTwoPower = (int)pow(...

by: Netwatcher 
last post by:
can somebody explain me where to put "{ }" and ";" symbols on a script?
i did search the web but didn't find any explanation written in a way i can understand.
example of a code that i tried and doesn't work
<script Language="JavaScript">
function distance()
}
alert("Point One");
var x = prompt("Enter a X variable for the first point", "X");
var y = prompt("Enter a Y variable for the first point", "Y");

by: marktang 
last post by:
ONU (Optical Network Unit) is one of the key components for providing highspeed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...

by: Oralloy 
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bitfields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++12 std=c++20 Wnarrowing bit_field.cpp
Here is the code in...
 
by: jinu1996 
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...

by: Hystou 
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...

by: agi2029 
last post by:
Let's talk about the concept of autonomous AI software engineers and nocode agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...

by: conductexam 
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...

by: TSSRALBI 
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LANtoLAN VPNs.
The last exercise I practiced was to create a LANtoLAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...

by: adsilva 
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
 
by: muto222 
last post by:
How can i add a mobile payment intergratation into php mysql website.
 