Integer exponentiation in Go

[Dean Schulze]

Go doesn't support the universal (except for Go) syntax 2**i for exponentiation.  The math/big package has the Exp function which does the same thing but this gives the following errors:

new(big.Int).Exp(2, i, 0)

 cannot use 2 (type int) as type *big.Int in function argument

 cannot use i (type int) as type *big.Int in function argument

 cannot use 0 (type int) as type *big.Int in function argument

  invalid operation: n * new(big.Int).Exp(2, i, 0) (mismatched types int and *big.Int)

Is there sane syntax to do integer exponentiation in go?

[Dave Cheney]

I'd question the notion that ** for exponentiation is universal,
http://stackoverflow.com/questions/213042/how-do-you-do-exponentiation-in-c.

If you're using a machine sized int, do you want math.Pow ?
http://godoc.org/math#Pow

> --
> 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/groups/opt_out.

[Dean Schulze]

math.Pow() is for float64.  I want integer exponentiation.  I can do it easy enough in a loop but there must be a better way.

[Rémy Oudompheng]

1<<i is the common way to compute 2 to the i-th power.
What is your use case?

Rémy.

[Alexei Sholik]

math.Pow() is for float64.  I want integer exponentiation.  I can do it easy enough in a loop but there must be a better way.

A better way would be to use fast exponentiation[1]. Go let's you code your exponentiation method of choice yourself which is quite fun.

There is also Exp for big ints[2].

[1]: http://en.wikipedia.org/wiki/Exponentiation_by_squaring

[2]: http://golang.org/pkg/math/big/#Int.Exp

--

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/groups/opt_out.

--
Best regards
Alexei Sholik

[Jan Mercl]

On Sat, Sep 21, 2013 at 6:41 AM, Dean Schulze <dean.w....@gmail.com> wrote:

func ModPowBigInt(b, e, m *big.Int) (r *big.Int)
func ModPowByte(b, e, m byte) byte
func ModPowUint16(b, e, m uint16) uint16
func ModPowUint32(b, e, m uint32) uint32
func ModPowUint64(b, e, m uint64) (r uint64)

http://godoc.org/github.com/cznic/mathutil

-j

[Michael Jones]

My code often contains:

// 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

}

Personally I wish for integer powers in the language. Much as I wish for min() and max() in the language: calling the function can be as expensive as doing the operation.

--
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/groups/opt_out.

--

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

[Jan Mercl]

On Sat, Sep 21, 2013 at 5:19 PM, Michael Jones <m...@google.com> wrote:
> Personally I wish for integer powers in the language. Much as I wish for
> min() and max() in the language: calling the function can be as expensive as
> doing the operation.

Theres fortunately no call, it's inlined (release 1.1.2/Linux/x86_64):

jnml@r630 ~/src/tmp $ ls
main.go
jnml@r630 ~/src/tmp $ cat main.go
package main

import (
"fmt"
)

func max(a, b int) int {
if a > b {
return a
}

return b
}

func main() {
fmt.Println(max(0xaaaa, 0xbbbb))
}
jnml@r630 ~/src/tmp $ go build && ls
main.go tmp
jnml@r630 ~/src/tmp $ gdb tmp
GNU gdb (GDB) 7.5.91.20130417-cvs-ubuntu
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/jnml/src/tmp/tmp...done.
warning: File "/home/jnml/go/src/pkg/runtime/runtime-gdb.py"
auto-loading has been declined by your `auto-load safe-path' set to
"$debugdir:$datadir/auto-load".
To enable execution of this file add
add-auto-load-safe-path /home/jnml/go/src/pkg/runtime/runtime-gdb.py
line to your configuration file "/home/jnml/.gdbinit".
To completely disable this security protection add
set auto-load safe-path /
line to your configuration file "/home/jnml/.gdbinit".
For more information about this security protection see the
"Auto-loading safe path" section in the GDB manual. E.g., run from the shell:
info "(gdb)Auto-loading safe path"
(gdb) b main.main
Breakpoint 1 at 0x400c00: file /home/jnml/src/tmp/main.go, line 15.
(gdb) r
Starting program: /home/jnml/src/tmp/tmp
warning: no loadable sections found in added symbol-file
system-supplied DSO at 0x7ffff7ffd000

Breakpoint 1, main.main () at /home/jnml/src/tmp/main.go:15
15 func main() {
(gdb) disassemble /m
Dump of assembler code for function main.main:
15 func main() {
=> 0x0000000000400c00 <+0>: mov %fs:0xfffffffffffffff0,%rcx
0x0000000000400c09 <+9>: cmp (%rcx),%rsp
0x0000000000400c0c <+12>: ja 0x400c13 <main.main+19>
0x0000000000400c0e <+14>: callq 0x41e3c0 <runtime.morestack00>
0x0000000000400c13 <+19>: sub $0x60,%rsp

16 fmt.Println(max(0xaaaa, 0xbbbb))
0x0000000000400c17 <+23>: mov $0xaaaa,%rcx
0x0000000000400c1e <+30>: mov $0xbbbb,%rax
0x0000000000400c25 <+37>: cmp %rax,%rcx
0x0000000000400c28 <+40>: jle 0x400c86 <main.main+134>
0x0000000000400c2a <+42>: lea 0x50(%rsp),%rdi
0x0000000000400c2f <+47>: xor %rax,%rax
0x0000000000400c32 <+50>: stos %rax,%es:(%rdi)
0x0000000000400c34 <+52>: stos %rax,%es:(%rdi)
0x0000000000400c36 <+54>: lea 0x50(%rsp),%rbx
0x0000000000400c3b <+59>: mov %rbx,0x30(%rsp)
0x0000000000400c40 <+64>: mov 0x30(%rsp),%rbx
0x0000000000400c45 <+69>: mov $0x1,%rsi
0x0000000000400c4c <+76>: mov $0x1,%rdx
0x0000000000400c53 <+83>: mov %rbx,0x38(%rsp)
0x0000000000400c58 <+88>: mov 0x38(%rsp),%rbx
0x0000000000400c5d <+93>: mov $0x4815c0,%eax
0x0000000000400c62 <+98>: mov %rax,(%rbx)
0x0000000000400c65 <+101>: mov %rcx,0x8(%rbx)
0x0000000000400c69 <+105>: mov 0x38(%rsp),%rbx
0x0000000000400c6e <+110>: mov %rbx,(%rsp)
0x0000000000400c72 <+114>: mov %rsi,0x8(%rsp)
0x0000000000400c77 <+119>: mov %rdx,0x10(%rsp)
0x0000000000400c7c <+124>: callq 0x421e30 <fmt.Println>
0x0000000000400c86 <+134>: mov %rax,%rcx
0x0000000000400c89 <+137>: jmp 0x400c2a <main.main+42>
0x0000000000400c8b <+139>: add %al,(%rax)
0x0000000000400c8d <+141>: add %al,(%rax)
0x0000000000400c8f <+143>: add %ah,-0x75(%rax,%rcx,2)

17 }
0x0000000000400c81 <+129>: add $0x60,%rsp
0x0000000000400c85 <+133>: retq

End of assembler dump.
(gdb)

-j

[Michael Jones]

That's very good! ;-)

If it were built in, such that the compiler knew you wanted MAX and MIN, then it could make use of various conditional moves or other instructions provided by the CPU. 

Also, as it is, you still need:

MinByte(a, b byte) byte

MinInt8(a, b int8) int8

MinInt16(a, b int16) int16

MinInt32(a, b int32) int32

MinInt64(a, b int64) int64

MinUint8(a, b uint8) uint8

MinUint16(a, b uint16) uint16

MinUint32(a, b uint32) uint32

MinUint64(a, b uint64) uint64

MinFloat32(a, b float32) float32

MinFloat64(a, b float64) float64

...but that's another topic. Glad that it is now inlined! Previously it was not.

[RickyS]

I have used this algorithm as well, and it works, and is faster than the 'naive' method.  For completeness, here's my version (no difference that I see):

// http://www.programminglogic.com/fast-exponentiation-algorithms/
func iPow(a, b int64) int64 {
  var result int64 = 1;

  for 0 != b {
    if 0 != (b & 1) {
      result *= a;

    }
    b >>= 1;
    a *= a;
  }

  return result;
}

As you can see, I cribbed it from a different web site.  That's all.
--------------------
On Saturday, September 21, 2013 6:19:39 PM UTC+3, Michael Jones wrote:

My code often contains:

...