How to calculate x^y? (the power of)

[Ondekoza]

How do I idiomatically calculate "the power of" with integers?

z := 3^4 // Nooo, ^ caret is bitwise negation
z := 3**4 // Nooo, invalid indirect
z := math.Pow(3,4) // Correct, but converting 3 and 4 to float, and the result.
BigInt? I cannot provide an example, because I cannot understand from the docs how to convert a 3 to a Bigint.

Is the big package (using ints) better or converting to float first (using the math-package)?
Would you see 2^x as a special case (using shifting)?

[Ross Light]

I would recommend either writing a PowInt function that performs the operation in a loop, or just cast the result from Pow.  As long as you don't need 64-bits of integer precision, math.Pow doesn't have a significant downside to it.

Cheers,

Ross

[chl]

I believe that using the big package is a little bit overkill if your not dealing with extremely large numbers.

I usually do what Ross has suggested but with one small little change. That is I use int64 instead of int because I deal with much larger numbers.

//Here how you convert 3 into a big.Int

b := big.NewInt(3) // the 3 must be an int64

[Lukasz]

Here are some algorithms you could have a look at: http://en.wikipedia.org/wiki/Exponentiation_by_squaring

[Job van der Zwan]

So, at the moment we have the packages math, math/big, math/complex and math/random. I assume that this is because for most types converting to and from float64 provides enough precision, so it's a decent one-size-fits-all approach, with complex and random packages providing specific functionality. 

However, in many cases all calculations are going to be using the same type: uint64 was the ideal type for my pixel-manipulations of image data, for example. Repeatedly casting to and from float64 for every pixel in the image would provide quite a lot of unnecessary overhead and unnecessary code. (Also, this is semi-related to the discussion here, which complains about the lack of implicit casting. I'm glad Go doesn't do this, but I do agree it's feels wasteful to repeatedly cast to and from float64 all the time)

Would it be worthwhile to add specific math packages for different types? They could reduce the necessity for explicit casting, and potentially could greatly increase the speed of a program (imagine casting to and from float64 for every colour channel for every pixel in a 20 megapixel picture).

There have been earlier discussions on this subject, like this one. This appears to be the general consensus:

On Monday, 1 August 2011 22:49:18 UTC+2, Alex Ray wrote:

Generics are difficult.  Either you end up defining special types with generic operations on them (a la pkg/sort) or you end up reflecting on yourself and burning a lot of performance and adding complexity.
At the worst case, all of them could be implemented and you have a more verbose library.  

So, here's my idea. This is the current math package:

math

math/big

math/cmplx

math/random

Let's say the following packages would be added:

math/i32

math/u32

math/i64

math/u64

(These names are just the first thing that came to mind, because they're short and it is immediately obvious which type they involve. The fact that they're similar to the names of the types they represent might cause confusion though, so better suggestions are welcome.)

The general rule would be that all functions in these packages take and return the type they're named after. So if the math you're going to do only involves uint64, for example, you could import math/u64. Then the answer to Ondekoza's question would become:

z := u64.Pow(3,4)

It's immediately obvious what the type of z is, and the algorithm involved can be optimised for that specific type. It also removes the need for typecasting in most cases, and where it would still be necessary (for example, when using a uint16 as the input) it's probably better to be explicit anyway. 

As far as I can see, it's not more verbose either - "u64" is one less character to write than "math" ;-). It's more explicit about the type used, but not more verbose, and explicitness seems kind of the point of using static typing and forcing explicit casting. Yes, it takes more code to implement, but the benefits would be better optimisations.

Thoughts?

[Ian Davis]

On Wed, Jul 11, 2012 at 6:11 PM, Job van der Zwan

> So, here's my idea. This is the current math package:
>
> math
> math/big
> math/cmplx
> math/random
>
> Let's say the following packages would be added:
>
> math/i32
> math/u32
> math/i64
> math/u64
>

I don't think there's any need to wait for extensions to be added to
the standard library. These could be implemented as independent
packages by the community and when they reach a good level of maturity
then the golang maintainers could consider bringing them into the
standard library.

You have some good ideas, there's no need to wait, just start coding
and see if others like the ideas too :)

Ian

[Job van der Zwan]

On Wednesday, 11 July 2012 23:27:50 UTC+2, Ian Davis wrote:

I don't think there's any need to wait for extensions to be added to
the standard library. These could be implemented as independent
packages by the community and when they reach a good level of maturity
then the golang maintainers could consider bringing them into the
standard library.

 

You have some good ideas, there's no need to wait, just start coding
and see if others like the ideas too :)

Ian

 

Thanks! I just made that up on the spot, so I had no idea if there were some obvious pitfalls that I was missing. Also, if I wanted to start a project like this I need to learn how to use Git or Mercurial properly first, and look up some fast integer math algorithms. The latter is especially intimidating - I'm kind of worried that any code I'll write will be thrown away anyway if somebody who Actually Knows His Stuff gets involved. ;-)

[Ian Davis]

I don't think that's a problem. If you can attract one of these people
to write code on your project then it can only be a positive. The best
thing to do is start something and then get some feedback. Great way
to learn the algorithms too!

Ian

[Job van der Zwan]

Ok, you convinced me, and I can't sleep anyway. I've got my free copy of "Version control by example" sitting next to me, and I just made this page:

http://code.google.com/p/intmath/

... and now, on to actually start coding some stuff!

[Job van der Zwan]

I get the feeling that page took a fairly simple concept and explained in a very difficult way. Thank the Flying Spaghetti Monster for simple English...

http://simple.wikipedia.org/wiki/Exponentiation_by_squaring

Ondekoza, I started with simple implementations of Abs and Pow, so if you want you could give otherwise empty library a try. What else would people like to see implemented?

On Wednesday, 11 July 2012 05:55:43 UTC+2, Lukasz wrote:

[Chris Hines]

Min and Max.

[Job van der Zwan]

Woah, I really need some sleep if I didn't even think of something as basic as that! :P Ok, will do that and then take a break.

Have to think about if and how to implement fixed point math, sin/cos functions (this looks like a good start) and of course any other request coming my way.

[++pac]

Looks fine! You mentioned pixel manipulation functions you work with, so,  please, feel free to contribute to my 'chroma' pkg, if you wish: https://code.google.com/p/chroma/
Peter

[Frithjof Schulze]

On Wed, Jul 11, 2012 at 07:52:55PM -0700, Job van der Zwan wrote:
> Ok, you convinced me, and I can't sleep anyway. I've got my free copy of
> "Version control by example" sitting next to me, and I just made this page:
>
> http://code.google.com/p/intmath/
>
> ... and now, on to actually start coding some stuff!

Do you know about these two projects?

https://bitbucket.org/SyntaxK/imath/src
https://github.com/cznic/mathutil

Both implement some integer arithmetic missing in the standard
library.

Best,
Frithjof

[Job van der Zwan]

Nope, thanks! I'll check those out.

[Thomas Bushnell, BSG]

On Wed, Jul 11, 2012 at 1:11 PM, Job van der Zwan <j.l.van...@gmail.com> wrote:

However, in many cases all calculations are going to be using the same type: uint64 was the ideal type for my pixel-manipulations of image data, for example. Repeatedly casting to and from float64 for every pixel in the image would provide quite a lot of unnecessary overhead and unnecessary code. (Also, this is semi-related to the discussion here, which complains about the lack of implicit casting. I'm glad Go doesn't do this, but I do agree it's feels wasteful to repeatedly cast to and from float64 all the time)

Most processors have a floating point exp operation, but do not have an integer exp operation.

Given that, I suspect the fastest method is indeed to do three floating point conversions and one floating point exp, rather than hand-roll an integer exponentiation by squaring.

So if the issue is only efficiency, use the math library. If the issue is typing speed:

func e(x y, int) int {

  u64(math.Pow(float64(x), float64(y)))

}

Thomas

[Job van der Zwan]

On Thursday, 12 July 2012 15:56:33 UTC+2, Thomas Bushnell, BSG wrote:

Most processors have a floating point exp operation, but do not have an integer exp operation.

Emphasis "most" - I wouldn't be surprised if my 32bit netbook prefers the integer option over the float64 option. Also, how would idiomatic Go code compile to something using that operation? I don't see any hint of that being implemented in the source:

http://golang.org/src/pkg/math/exp.go

Or is there source file with assembly specific optimisations that I've forgotten to notice?

[John Asmuth]

On Thursday, July 12, 2012 10:41:48 AM UTC-4, Job van der Zwan wrote:

Or is there source file with assembly specific optimisations that I've forgotten to notice?

Perhaps :)

http://golang.org/src/pkg/math/exp_amd64.s 

[Thomas Bushnell, BSG]

You're looking at math.exp (unexported) not math.Exp. The former is there for a fallback for systems where there isn't a faster version in assembly.

I don't know what "integer option" you are referring to on your 32bit netbook. I don't claim to be an expert on the ever-changing x86 instruction set, but I'm pretty sure there is no integer exponentiation instruction still. (And as the assembly from John Asmuth points out to me, there isn't a floating point exp instruction either, so my previous argument is likely incorrect.)

[Job van der Zwan]

On Thursday, 12 July 2012 16:51:41 UTC+2, Thomas Bushnell, BSG wrote:

You're looking at math.exp (unexported) not math.Exp. The former is there for a fallback for systems where there isn't a faster version in assembly.

I don't know what "integer option" you are referring to on your 32bit netbook. I don't claim to be an expert on the ever-changing x86 instruction set, but I'm pretty sure there is no integer exponentiation instruction still. (And as the assembly from John Asmuth points out to me, there isn't a floating point exp instruction either, so my previous argument is likely incorrect.)

I meant the plain-Go-using-integers code, sorry for the confusion. I'll try to benchmark it later - only way to find out, right?

On Thursday, 12 July 2012 16:47:10 UTC+2, John Asmuth wrote:

Perhaps :)

http://golang.org/src/pkg/math/exp_amd64.s 

Thanks, both of you. This is quite an educational experience :) .

[Job van der Zwan]

On Thursday, 12 July 2012 15:56:33 UTC+2, Thomas Bushnell, BSG wrote:

Given that, I suspect the fastest method is indeed to do three floating point conversions and one floating point exp, rather than hand-roll an integer exponentiation by squaring.

So, I promised benchmarks. Benchmark code here, results on my EEE 1005HA (32 bit, Atom N280):

BenchmarkExpInt64   500000       5784 ns/op

BenchmarkExpFloat64ToInt64   200000       8023 ns/op

BenchmarkExpInt32  1000000       2028 ns/op

BenchmarkExpFloat64ToInt32   200000       8445 ns/op

ok   intmath 8.484s

So it seems likely that on older hardware, using libraries like this is worth it (assuming my benchmark isn't flawed).

So if the issue is only efficiency, use the math library. If the issue is typing speed:

func e(x y, int) int {

  u64(math.Pow(float64(x), float64(y)))

}

 

Don't you mean uint64? Did you just prove my worry about potential confusing package names was correct? ;-) 

[Aurélien Desbrières]

Hi Ross,

Golang spec have nothing about "PowInt function", can you elaborate please?

[Michael Jones]

Exponentiation is not a built-in operator in Go, C, C++, and a number of other languages. It has always been a built-in in FORTRAN, BASIC, and others.

What one does in exponentiation-unaware language is to build simple functions for the task:

// Integer power: compute a**b using binary powering algorithm

// See Donald Knuth, The Art of Computer Programming, Volume 2, Section 4.6.3

func Pow(a, b int) int {

p := 1

for b > 0 {

if b&1 != 0 {

p *= a

}

b >>= 1

a *= a

}

return p

}

// Modular integer power: compute a**b mod m using binary powering algorithm

func PowMod(a, b, m int) int {

a = a % m

p := 1 % m

for b > 0 {

if b&1 != 0 {

p = (p * a) % m

}

b >>= 1

a = (a * a) % m

}

return p

}

The two above are in my “tools” directory, along with min, max, Hamming distance, bit count, and other universally useful functions not a standard part of Go. Use the first one and you’ll be fine. The second is for when you want A**B mod M, and A**B might overflow…is is safer to compute the intermediate values mod M.

Michael 

— 

Michael Jones, CEO  •  mic...@wearality.com  •  +1 650 656-6989 

Wearality Corporation  •  289 S. San Antonio Road  •  Los Altos, CA 94022

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Louki Sumirniy]

math/big's big.Int has a power function: https://golang.org/pkg/math/big/#Int.Exp

I wrote a power function for big.Float you can find here: https://github.com/l0k1verloren/float256/blob/master/float256.go#L82 It doesn't check for overflows because I don't think big.Float overflows from 64 bit exponents though maybe it could from a big enough base.

[dhaval...@gmail.com]

Modular power in Golang  

func power(x,y,p int64) int64 { var res int64 res = 1; // Initialize result x =(x%p)%mod; // Update x if it is more than or // equal to p for y>0{ // If y is odd, multiply x with result if y & 1==1{ res = ((res*x)%p)%mod; } // y must be even now y = y/2; x = ((x*x)%p)%mod; } return res; }