number

Documentation

Index

• func BaseExp(N int, eps ...float64) (int, int, bool)
• func ContinuedFraction(real float64, eps ...float64) []int
• func Convergent(cfx []int) (int, int, float64)
• func FindOrder(a, N int, binary string, eps ...float64) (int, int, float64, bool)
• func GCD(a, b int) int
• func IsEven(v int) bool
• func IsOdd(v int) bool
• func IsPrime(N int) bool
• func IsTrivial(N int, factor ...int) bool
• func Log2(N int) (int, error)
• func ModExp(a, r, N int) int
• func ModExp2(a, j, N int) int
• func Must[T any](v T, err error) T
• func ParseFloat(binary string) (float64, error)
• func Pow(a, r int) int
• func Sum(p []float64) float64

Examples

• BaseExp
• ContinuedFraction
• Convergent
• FindOrder (Mod15)
• FindOrder (Mod21a2)
• FindOrder (Mod21a4)
• GCD
• IsTrivial
• Log2
• ModExp
• ModExp2
• ParseFloat

Functions

func BaseExp

func BaseExp(N int, eps ...float64) (int, int, bool)

BaseExp returns a and b such that a**b == N. If N is not a power of a, return false.

Example

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	a, b, ok := number.BaseExp(125)
	fmt.Printf("%v^%v %v", a, b, ok)

}

Output:

5^3 true

func ContinuedFraction

func ContinuedFraction(real float64, eps ...float64) []int

ContienuedFraction returns a continued fraction of real. if eps is empty, epsilon.E3 is used.

Example

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	c := number.ContinuedFraction(0.8125)
	s, r, d := number.Convergent(c)
	fmt.Printf("%v %v/%v=%v\n", c, s, r, d)

}

Output:

[0 1 4 3] 13/16=0.8125

func Convergent

func Convergent(cfx []int) (int, int, float64)

Convergent returns a convergent of continued fraction.

Example

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	m := "0.00101010101"
	v, err := number.ParseFloat(m)
	fmt.Printf("%v=%v %v\n", m, v, err)

	c := number.ContinuedFraction(v)
	for i := 0; i < len(c); i++ {
		s, r, d := number.Convergent(c[:i+1])
		fmt.Printf("%v: %v/%v=%v\n", c[:i+1], s, r, d)
	}

}

Output:

0.00101010101=0.16650390625 <nil>
[0]: 0/1=0
[0 6]: 1/6=0.16666666666666666
[0 6 170]: 170/1021=0.1665034280117532
[0 6 170 1]: 171/1027=0.1665043816942551
[0 6 170 1 1]: 341/2048=0.16650390625

func FindOrder

func FindOrder(a, N int, binary string, eps ...float64) (int, int, float64, bool)

FindOrder returns convergent s/r and its real number such that a**r mod N = 1.

Example (Mod15)

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	s, r, d, ok := number.FindOrder(7, 15, "0.110")
	fmt.Printf("%v/%v=%v %v\n", s, r, d, ok)
	fmt.Printf("%d^%d mod %d = %v\n", 7, r, 15, number.ModExp(7, r, 15))

}

Output:

3/4=0.75 true
7^4 mod 15 = 1

Example (Mod21a2)

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	s, r, d, ok := number.FindOrder(2, 21, "0.001010101")
	fmt.Printf("%v/%v=%v %v\n", s, r, d, ok)
	fmt.Printf("%d^%d mod %d = %v\n", 2, r, 21, number.ModExp(2, r, 21))

}

Output:

1/6=0.16666666666666666 true
2^6 mod 21 = 1

Example (Mod21a4)

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	s, r, d, ok := number.FindOrder(4, 21, "0.01010101")
	fmt.Printf("%v/%v=%v %v\n", s, r, d, ok)
	fmt.Printf("%d^%d mod %d = %v\n", 4, r, 21, number.ModExp(4, r, 21))

}

Output:

1/3=0.3333333333333333 true
4^3 mod 21 = 1

func GCD

func GCD(a, b int) int

GCD returns the greatest common divisor of a and b.

Example

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	gcd := number.GCD(15, 7)
	fmt.Println(gcd)

}

Output:

1

func IsEven

func IsEven(v int) bool

IsEven returns true if v is even number.

func IsOdd

func IsOdd(v int) bool

IsOdd returns true if v is odd number.

func IsPrime

func IsPrime(N int) bool

IsPrime returns true if N is prime number.

func IsTrivial

func IsTrivial(N int, factor ...int) bool

IsTrivial returns true if factor is trivial factor of N.

Example

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	fmt.Println(number.IsTrivial(21, 1, 21))
	fmt.Println(number.IsTrivial(21, 1, 7))

}

Output:

true
false

func Log2

func Log2(N int) (int, error)

Log2 returns the base 2 logarithm of N. N must be a power of 2.

Example

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	fmt.Println(number.Log2(8))
	fmt.Println(number.Log2(32))
	fmt.Println(number.Log2(15))
	fmt.Println(number.Log2(20))

}

Output:

3 <nil>
5 <nil>
-1 N must be a power of 2
-1 N must be a power of 2

func ModExp

func ModExp(a, r, N int) int

ModExp returns a**r mod N.

Example

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	// 4^3 mod 21
	v := number.ModExp(4, 3, 21)
	fmt.Println(v)

}

Output:

1

func ModExp2

func ModExp2(a, j, N int) int

ModExp2 returns a**(2**j) mod N.

Example

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	// 7^2^4 mod 15
	v := number.ModExp2(7, 4, 15)
	fmt.Println(v)

}

Output:

1

func Must

func Must[T any](v T, err error) T

Must returns v if err is nil, otherwise panic.

func ParseFloat

func ParseFloat(binary string) (float64, error)

ParseFloat returns float64 from binary string.

Example

package main

import (
	"fmt"

	"github.com/itsubaki/q/math/number"
)

func main() {
	// 0.101 -> 1/2 + 1/8 = 0.5 + 0.125 = 0.625
	f, err := number.ParseFloat("0.101")
	fmt.Println(f, err)

}

Output:

0.625 <nil>

func Pow

func Pow(a, r int) int

Pow returns a**r, the base-a exponential of r.

func Sum

func Sum(p []float64) float64

Sum returns the sum of p.