New Upstream Release - golang-github-remyoudompheng-bigfft
Ready changes
Summary
Merged new upstream version: 0.0+git20230129.24d4a6f (was: 0.0+git20190728.6a916e3).
Diff
diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
new file mode 100644
index 0000000..ae817de
--- /dev/null
+++ b/.github/workflows/main.yml
@@ -0,0 +1,22 @@
+name: Unit tests
+
+on:
+ push:
+ branches: [ "master" ]
+ pull_request:
+ branches: [ "master" ]
+
+jobs:
+ build:
+ runs-on: ubuntu-latest
+ strategy:
+ matrix:
+ go: [ '~1.12', '~1.17', 'oldstable', 'stable' ]
+ name: Test with Go ${{ matrix.go }}
+ steps:
+ - uses: actions/checkout@v3
+ - name: Setup go
+ uses: actions/setup-go@v3
+ with:
+ go-version: ${{ matrix.go }}
+ - run: go test
diff --git a/README b/README
index 303c617..0fcd39d 100644
--- a/README
+++ b/README
@@ -1,3 +1,14 @@
+This library is a toy proof-of-concept implementation of the
+well-known Schonhage-Strassen method for multiplying integers.
+It is not expected to have a real life usecase outside number
+theory computations, nor is it expected to be used in any production
+system.
+
+If you are using it in your project, you may want to carefully
+examine the actual requirement or problem you are trying to solve.
+
+# Comparison with the standard library and GMP
+
Benchmarking math/big vs. bigfft
Number size old ns/op new ns/op delta
diff --git a/arith_386.s b/arith_386.s
deleted file mode 100644
index cc50a01..0000000
--- a/arith_386.s
+++ /dev/null
@@ -1,36 +0,0 @@
-// Trampolines to math/big assembly implementations.
-
-#include "textflag.h"
-
-// func addVV(z, x, y []Word) (c Word)
-TEXT ·addVV(SB),NOSPLIT,$0
- JMP math∕big·addVV(SB)
-
-// func subVV(z, x, y []Word) (c Word)
-TEXT ·subVV(SB),NOSPLIT,$0
- JMP math∕big·subVV(SB)
-
-// func addVW(z, x []Word, y Word) (c Word)
-TEXT ·addVW(SB),NOSPLIT,$0
- JMP math∕big·addVW(SB)
-
-// func subVW(z, x []Word, y Word) (c Word)
-TEXT ·subVW(SB),NOSPLIT,$0
- JMP math∕big·subVW(SB)
-
-// func shlVU(z, x []Word, s uint) (c Word)
-TEXT ·shlVU(SB),NOSPLIT,$0
- JMP math∕big·shlVU(SB)
-
-// func shrVU(z, x []Word, s uint) (c Word)
-TEXT ·shrVU(SB),NOSPLIT,$0
- JMP math∕big·shrVU(SB)
-
-// func mulAddVWW(z, x []Word, y, r Word) (c Word)
-TEXT ·mulAddVWW(SB),NOSPLIT,$0
- JMP math∕big·mulAddVWW(SB)
-
-// func addMulVVW(z, x []Word, y Word) (c Word)
-TEXT ·addMulVVW(SB),NOSPLIT,$0
- JMP math∕big·addMulVVW(SB)
-
diff --git a/arith_amd64.s b/arith_amd64.s
deleted file mode 100644
index 0b79335..0000000
--- a/arith_amd64.s
+++ /dev/null
@@ -1,38 +0,0 @@
-// Trampolines to math/big assembly implementations.
-
-#include "textflag.h"
-
-// func addVV(z, x, y []Word) (c Word)
-TEXT ·addVV(SB),NOSPLIT,$0
- JMP math∕big·addVV(SB)
-
-// func subVV(z, x, y []Word) (c Word)
-// (same as addVV except for SBBQ instead of ADCQ and label names)
-TEXT ·subVV(SB),NOSPLIT,$0
- JMP math∕big·subVV(SB)
-
-// func addVW(z, x []Word, y Word) (c Word)
-TEXT ·addVW(SB),NOSPLIT,$0
- JMP math∕big·addVW(SB)
-
-// func subVW(z, x []Word, y Word) (c Word)
-// (same as addVW except for SUBQ/SBBQ instead of ADDQ/ADCQ and label names)
-TEXT ·subVW(SB),NOSPLIT,$0
- JMP math∕big·subVW(SB)
-
-// func shlVU(z, x []Word, s uint) (c Word)
-TEXT ·shlVU(SB),NOSPLIT,$0
- JMP math∕big·shlVU(SB)
-
-// func shrVU(z, x []Word, s uint) (c Word)
-TEXT ·shrVU(SB),NOSPLIT,$0
- JMP math∕big·shrVU(SB)
-
-// func mulAddVWW(z, x []Word, y, r Word) (c Word)
-TEXT ·mulAddVWW(SB),NOSPLIT,$0
- JMP math∕big·mulAddVWW(SB)
-
-// func addMulVVW(z, x []Word, y Word) (c Word)
-TEXT ·addMulVVW(SB),NOSPLIT,$0
- JMP math∕big·addMulVVW(SB)
-
diff --git a/arith_arm.s b/arith_arm.s
deleted file mode 100644
index 0ed60f5..0000000
--- a/arith_arm.s
+++ /dev/null
@@ -1,36 +0,0 @@
-// Trampolines to math/big assembly implementations.
-
-#include "textflag.h"
-
-// func addVV(z, x, y []Word) (c Word)
-TEXT ·addVV(SB),NOSPLIT,$0
- B math∕big·addVV(SB)
-
-// func subVV(z, x, y []Word) (c Word)
-TEXT ·subVV(SB),NOSPLIT,$0
- B math∕big·subVV(SB)
-
-// func addVW(z, x []Word, y Word) (c Word)
-TEXT ·addVW(SB),NOSPLIT,$0
- B math∕big·addVW(SB)
-
-// func subVW(z, x []Word, y Word) (c Word)
-TEXT ·subVW(SB),NOSPLIT,$0
- B math∕big·subVW(SB)
-
-// func shlVU(z, x []Word, s uint) (c Word)
-TEXT ·shlVU(SB),NOSPLIT,$0
- B math∕big·shlVU(SB)
-
-// func shrVU(z, x []Word, s uint) (c Word)
-TEXT ·shrVU(SB),NOSPLIT,$0
- B math∕big·shrVU(SB)
-
-// func mulAddVWW(z, x []Word, y, r Word) (c Word)
-TEXT ·mulAddVWW(SB),NOSPLIT,$0
- B math∕big·mulAddVWW(SB)
-
-// func addMulVVW(z, x []Word, y Word) (c Word)
-TEXT ·addMulVVW(SB),NOSPLIT,$0
- B math∕big·addMulVVW(SB)
-
diff --git a/arith_arm64.s b/arith_arm64.s
deleted file mode 100644
index 0ed60f5..0000000
--- a/arith_arm64.s
+++ /dev/null
@@ -1,36 +0,0 @@
-// Trampolines to math/big assembly implementations.
-
-#include "textflag.h"
-
-// func addVV(z, x, y []Word) (c Word)
-TEXT ·addVV(SB),NOSPLIT,$0
- B math∕big·addVV(SB)
-
-// func subVV(z, x, y []Word) (c Word)
-TEXT ·subVV(SB),NOSPLIT,$0
- B math∕big·subVV(SB)
-
-// func addVW(z, x []Word, y Word) (c Word)
-TEXT ·addVW(SB),NOSPLIT,$0
- B math∕big·addVW(SB)
-
-// func subVW(z, x []Word, y Word) (c Word)
-TEXT ·subVW(SB),NOSPLIT,$0
- B math∕big·subVW(SB)
-
-// func shlVU(z, x []Word, s uint) (c Word)
-TEXT ·shlVU(SB),NOSPLIT,$0
- B math∕big·shlVU(SB)
-
-// func shrVU(z, x []Word, s uint) (c Word)
-TEXT ·shrVU(SB),NOSPLIT,$0
- B math∕big·shrVU(SB)
-
-// func mulAddVWW(z, x []Word, y, r Word) (c Word)
-TEXT ·mulAddVWW(SB),NOSPLIT,$0
- B math∕big·mulAddVWW(SB)
-
-// func addMulVVW(z, x []Word, y Word) (c Word)
-TEXT ·addMulVVW(SB),NOSPLIT,$0
- B math∕big·addMulVVW(SB)
-
diff --git a/arith_decl.go b/arith_decl.go
index 7659b01..96937df 100644
--- a/arith_decl.go
+++ b/arith_decl.go
@@ -4,13 +4,30 @@
package bigfft
-import . "math/big"
+import (
+ "math/big"
+ _ "unsafe"
+)
-// implemented in arith_$GOARCH.s
+type Word = big.Word
+
+//go:linkname addVV math/big.addVV
func addVV(z, x, y []Word) (c Word)
+
+//go:linkname subVV math/big.subVV
func subVV(z, x, y []Word) (c Word)
+
+//go:linkname addVW math/big.addVW
func addVW(z, x []Word, y Word) (c Word)
+
+//go:linkname subVW math/big.subVW
func subVW(z, x []Word, y Word) (c Word)
+
+//go:linkname shlVU math/big.shlVU
func shlVU(z, x []Word, s uint) (c Word)
+
+//go:linkname mulAddVWW math/big.mulAddVWW
func mulAddVWW(z, x []Word, y, r Word) (c Word)
+
+//go:linkname addMulVVW math/big.addMulVVW
func addMulVVW(z, x []Word, y Word) (c Word)
diff --git a/arith_mips64x.s b/arith_mips64x.s
deleted file mode 100644
index 8244388..0000000
--- a/arith_mips64x.s
+++ /dev/null
@@ -1,40 +0,0 @@
-// Trampolines to math/big assembly implementations.
-
-// +build mips64 mips64le
-
-#include "textflag.h"
-
-// func addVV(z, x, y []Word) (c Word)
-TEXT ·addVV(SB),NOSPLIT,$0
- JMP math∕big·addVV(SB)
-
-// func subVV(z, x, y []Word) (c Word)
-// (same as addVV except for SBBQ instead of ADCQ and label names)
-TEXT ·subVV(SB),NOSPLIT,$0
- JMP math∕big·subVV(SB)
-
-// func addVW(z, x []Word, y Word) (c Word)
-TEXT ·addVW(SB),NOSPLIT,$0
- JMP math∕big·addVW(SB)
-
-// func subVW(z, x []Word, y Word) (c Word)
-// (same as addVW except for SUBQ/SBBQ instead of ADDQ/ADCQ and label names)
-TEXT ·subVW(SB),NOSPLIT,$0
- JMP math∕big·subVW(SB)
-
-// func shlVU(z, x []Word, s uint) (c Word)
-TEXT ·shlVU(SB),NOSPLIT,$0
- JMP math∕big·shlVU(SB)
-
-// func shrVU(z, x []Word, s uint) (c Word)
-TEXT ·shrVU(SB),NOSPLIT,$0
- JMP math∕big·shrVU(SB)
-
-// func mulAddVWW(z, x []Word, y, r Word) (c Word)
-TEXT ·mulAddVWW(SB),NOSPLIT,$0
- JMP math∕big·mulAddVWW(SB)
-
-// func addMulVVW(z, x []Word, y Word) (c Word)
-TEXT ·addMulVVW(SB),NOSPLIT,$0
- JMP math∕big·addMulVVW(SB)
-
diff --git a/arith_mipsx.s b/arith_mipsx.s
deleted file mode 100644
index 6c0e92e..0000000
--- a/arith_mipsx.s
+++ /dev/null
@@ -1,40 +0,0 @@
-// Trampolines to math/big assembly implementations.
-
-// +build mips mipsle
-
-#include "textflag.h"
-
-// func addVV(z, x, y []Word) (c Word)
-TEXT ·addVV(SB),NOSPLIT,$0
- JMP math∕big·addVV(SB)
-
-// func subVV(z, x, y []Word) (c Word)
-// (same as addVV except for SBBQ instead of ADCQ and label names)
-TEXT ·subVV(SB),NOSPLIT,$0
- JMP math∕big·subVV(SB)
-
-// func addVW(z, x []Word, y Word) (c Word)
-TEXT ·addVW(SB),NOSPLIT,$0
- JMP math∕big·addVW(SB)
-
-// func subVW(z, x []Word, y Word) (c Word)
-// (same as addVW except for SUBQ/SBBQ instead of ADDQ/ADCQ and label names)
-TEXT ·subVW(SB),NOSPLIT,$0
- JMP math∕big·subVW(SB)
-
-// func shlVU(z, x []Word, s uint) (c Word)
-TEXT ·shlVU(SB),NOSPLIT,$0
- JMP math∕big·shlVU(SB)
-
-// func shrVU(z, x []Word, s uint) (c Word)
-TEXT ·shrVU(SB),NOSPLIT,$0
- JMP math∕big·shrVU(SB)
-
-// func mulAddVWW(z, x []Word, y, r Word) (c Word)
-TEXT ·mulAddVWW(SB),NOSPLIT,$0
- JMP math∕big·mulAddVWW(SB)
-
-// func addMulVVW(z, x []Word, y Word) (c Word)
-TEXT ·addMulVVW(SB),NOSPLIT,$0
- JMP math∕big·addMulVVW(SB)
-
diff --git a/arith_ppc64x.s b/arith_ppc64x.s
deleted file mode 100644
index 16c7f15..0000000
--- a/arith_ppc64x.s
+++ /dev/null
@@ -1,38 +0,0 @@
-// Trampolines to math/big assembly implementations.
-
-// +build ppc64 ppc64le
-
-#include "textflag.h"
-
-// func addVV(z, x, y []Word) (c Word)
-TEXT ·addVV(SB),NOSPLIT,$0
- BR math∕big·addVV(SB)
-
-// func subVV(z, x, y []Word) (c Word)
-TEXT ·subVV(SB),NOSPLIT,$0
- BR math∕big·subVV(SB)
-
-// func addVW(z, x []Word, y Word) (c Word)
-TEXT ·addVW(SB),NOSPLIT,$0
- BR math∕big·addVW(SB)
-
-// func subVW(z, x []Word, y Word) (c Word)
-TEXT ·subVW(SB),NOSPLIT,$0
- BR math∕big·subVW(SB)
-
-// func shlVU(z, x []Word, s uint) (c Word)
-TEXT ·shlVU(SB),NOSPLIT,$0
- BR math∕big·shlVU(SB)
-
-// func shrVU(z, x []Word, s uint) (c Word)
-TEXT ·shrVU(SB),NOSPLIT,$0
- BR math∕big·shrVU(SB)
-
-// func mulAddVWW(z, x []Word, y, r Word) (c Word)
-TEXT ·mulAddVWW(SB),NOSPLIT,$0
- BR math∕big·mulAddVWW(SB)
-
-// func addMulVVW(z, x []Word, y Word) (c Word)
-TEXT ·addMulVVW(SB),NOSPLIT,$0
- BR math∕big·addMulVVW(SB)
-
diff --git a/debian/changelog b/debian/changelog
index d609b3e..a1ec04a 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,3 +1,9 @@
+golang-github-remyoudompheng-bigfft (0.0+git20230129.24d4a6f-1) UNRELEASED; urgency=low
+
+ * New upstream snapshot.
+
+ -- Debian Janitor <janitor@jelmer.uk> Wed, 07 Jun 2023 15:45:42 -0000
+
golang-github-remyoudompheng-bigfft (0.0+git20190728.6a916e3-2) unstable; urgency=medium
[ Debian Janitor ]
diff --git a/fermat_test.go b/fermat_test.go
index f9db5ba..b1105d8 100644
--- a/fermat_test.go
+++ b/fermat_test.go
@@ -2,10 +2,14 @@ package bigfft
import (
"fmt"
- . "math/big"
+ "math/big"
"testing"
)
+type (
+ Int = big.Int
+)
+
// parseHex reads an hex-formatted number modulo 2^bits+1.
func parseHex(s string, bits int) fermat {
z := new(Int)
@@ -35,9 +39,9 @@ func TestFermatShift(t *testing.T) {
for i := 0; i < n; i++ {
f[i] = Word(rnd.Int63())
}
- b := NewInt(1)
+ b := big.NewInt(1)
b = b.Lsh(b, uint(n*_W))
- b = b.Add(b, NewInt(1))
+ b = b.Add(b, big.NewInt(1))
z := make(fermat, len(f)) // Test with uninitialized z.
for shift := -2048; shift < 2048; shift++ {
z.Shift(f, shift)
@@ -61,9 +65,9 @@ func TestFermatShiftHalf(t *testing.T) {
for i := 0; i < n; i++ {
f[i] = ^Word(0)
}
- b := NewInt(1)
+ b := big.NewInt(1)
b = b.Lsh(b, uint(n*_W))
- b = b.Add(b, NewInt(1))
+ b = b.Add(b, big.NewInt(1))
z := make(fermat, len(f)) // Test with uninitialized z.
tmp := make(fermat, len(f))
tmp2 := make(fermat, len(f))
diff --git a/fft_test.go b/fft_test.go
index e1e1126..f7fb0cb 100644
--- a/fft_test.go
+++ b/fft_test.go
@@ -2,7 +2,7 @@ package bigfft
import (
"fmt"
- . "math/big"
+ "math/big"
"math/rand"
"testing"
)
@@ -342,10 +342,10 @@ func BenchmarkMulFFT_5x20Mb(b *testing.B) { benchmarkMulFFT(b, 5e6, 20e6) }
func BenchmarkMulFFT_5x50Mb(b *testing.B) { benchmarkMulFFT(b, 5e6, 50e6) }
func TestIssue1(t *testing.T) {
- e := NewInt(1)
+ e := big.NewInt(1)
e.SetBit(e, 132048, 1)
- e.Sub(e, NewInt(4)) // e == 1<<132048 - 4
- g := NewInt(0).Set(e)
+ e.Sub(e, big.NewInt(4)) // e == 1<<132048 - 4
+ g := big.NewInt(0).Set(e)
e.Mul(e, e)
g = Mul(g, g)
if g.Cmp(e) != 0 {