Change big.Int number between even<>odd

Hello, my code produces a big.Int number as follows:

package main

import (
	"fmt"
	"crypto/sha256"
	"math/big"
	"golang.org/x/crypto/blake2b"
)

func main() {
	test := "hello"
	h := sha256.New()
	s := fmt.Sprintf("%v", test)
	sum := h.Sum([]byte(s))
	hash := blake2b.Sum256(sum)
	zz := new(big.Int)
	zz.SetBytes(hash[:])
	fmt.Println(zz)
}

I need to increment zz by one. Can someone suggest on how to do this most efficiently? I was thinking the most efficient way is to XOR the least significant bit in zz but I’m not sure how to do it in Go.
Thanks

1 Like

I got one using the NOT gate and 2-complement route (named methodA). methodB is the standard Add 1.

package main

import (
	"fmt"
	"math/big"
)

func methodB(x *big.Int) {
	x.Add(x, big.NewInt(1))
}

func methodA(x *big.Int) {
	x.Not(x)
	x.Neg(x)
}

func main() {
	hash := []byte("8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf730")

	zz := new(big.Int)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method A: %s\n", zz.String())
	methodA(zz)
	fmt.Printf("AFTER method A : %s\n", zz.String())

	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method B: %s\n", zz.String())
	methodB(zz)
	fmt.Printf("AFTER method B : %s\n", zz.String())
}
// Output:
// BEFORE method A: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154864
// AFTER method A : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154865
// BEFORE method B: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154864
// AFTER method B : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154865

Benchmark both of them on my local system yields:

goos: linux
goarch: amd64
pkg: gosandbox
BenchmarkMethodA-8      25956531                44.1 ns/op
BenchmarkMethodB-8      17653945                65.8 ns/op
PASS
ok      gosandbox       2.425s
Benchmark Codes
package main

import (
	"math/big"
	"testing"
)

func BenchmarkMethodA(b *testing.B) {
	tgt := new(big.Int)
	hash := []byte("8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf730")

	for i := 0; i < b.N; i++ {
		tgt.SetBytes(hash[:])
		methodA(tgt)
	}
}

func BenchmarkMethodB(b *testing.B) {
	tgt := new(big.Int)
	hash := []byte("8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf730")

	for i := 0; i < b.N; i++ {
		tgt.SetBytes(hash[:])
		methodB(tgt)
	}
}

Not much of gains over readability compared to methodB.

You might need to run the benchmark tests on your system with all the proposals.

4 Likes

This will increment even numbers and decrement odd numbers…

2 Likes

This algorithm (b = not(a); b = neg(b)) to increment a number is impressively elegant.

2 Likes

haha. Thanks. Too bad the performance gain is not much. I’m still exploring other logic gates see what else I can come up with.

Currently, my hands are tied to a cryptography research work. :sweat:

1 Like

Maybe it’s faster to use byte operations directly instead of bigInt.
The problem with not and neg is that they need to modify all bytes. While an increment may need to modify just a few bytes. Not sure why the OP need a bigInt.

Here is an increment applied on the byte slice:

i := len(hash)-1
for i >= 0 {
    hash[i]++
    if hash[i] != 0 {
        break
    }
    i--
}
if i < 0 {
    // overflows
}
// assign the resulting hash to a bigInt if needed. 

It is very unlikely that the increment overflows because it can only occur when all bits are 1 in the initial number.

2 Likes

Tested the []byte arithmetic (named methodC). Performance is way out due to too many necessary guarding.

goos: linux
goarch: amd64
pkg: gosandbox
BenchmarkMethodA-8      26528644                43.5 ns/op
BenchmarkMethodB-8      17427963                66.9 ns/op
BenchmarkMethodC-8       6186016               194 ns/op
PASS
ok      gosandbox       3.835s

Code
package main

import (
	"fmt"
	"math/big"
	"strings"
)

func methodC(shasum string) string {
	if shasum == "" {
		return shasum
	}

	shasum = strings.ToLower(shasum)
	s := []byte(shasum)
	length := len(s)
	index := 0
	for i := 0; i < length; i++ {
		index = length - 1 - i
		x := &s[index : index+1][0]

		// if char is 0xf, carry forward and continue
		if *x == 102 {
			*x = 48 // set to 0x0
			continue
		}

		// if char is 0x9, increment to 0xa
		if *x == 57 {
			*x = 97 // set to 0xa
			break
		}

		// char is within incremental range
		*x += 1
		break
	}

	return string(s)
}

func methodB(x *big.Int) {
	x.Add(x, big.NewInt(1))
}

func methodA(x *big.Int) {
	x.Not(x)
	x.Neg(x)
}

func main() {
	shasum := "8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf730"
	zz := new(big.Int)

	hash := []byte(shasum)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method A: %s\n", zz.String())
	methodA(zz)
	fmt.Printf("AFTER method A : %s\n", zz.String())

	hash = []byte(shasum)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method B: %s\n", zz.String())
	methodB(zz)
	fmt.Printf("AFTER method B : %s\n", zz.String())

	hash = []byte(shasum)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method C: %s\n", zz.String())
	hash = []byte(methodC(shasum))
	zz.SetBytes(hash[:])
	fmt.Printf("AFTER method C: %s\n", zz.String())

}
// Output:
// BEFORE method A: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154864
// AFTER method A : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154865
// BEFORE method B: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154864
// AFTER method B : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154865
// BEFORE method C: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154864
// AFTER method C: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154865
Benchmark Code
package main

import (
	"math/big"
	"testing"
)

const (
	shasum = "8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf730"
)

func BenchmarkMethodA(b *testing.B) {
	tgt := new(big.Int)

	for i := 0; i < b.N; i++ {
		hash := []byte(shasum)
		tgt.SetBytes(hash[:])
		methodA(tgt)
	}
}

func BenchmarkMethodB(b *testing.B) {
	tgt := new(big.Int)

	for i := 0; i < b.N; i++ {
		hash := []byte(shasum)
		tgt.SetBytes(hash[:])
		methodB(tgt)
	}
}

func BenchmarkMethodC(b *testing.B) {
	tgt := new(big.Int)

	for i := 0; i < b.N; i++ {
		hash := []byte(methodC(shasum))
		tgt.SetBytes(hash[:])
	}
}

Also, I would avoid it since we’re re-inventing arithmetic stuff and it’s too complex. I tested the edge value 0x3f, the big.Int parsing does not agree although hex values agree to each other.

shasum := "8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf73f"
BEFORE method C: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154918
DEBUG BEFORE: 8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf73f
DEBUG AFTER : 8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf740
AFTER method C: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721155120



Disclaimer to any other readers

I’m just experimenting []byte arithmetic operations out of curiosity. Please do not go all out flaming me that I do something paranoid or set some weird rules about math and processor again.

1 Like

Why is shasum a string ? The algorithm is intended to operate on a byte slice/array as returned by blake2b.Sum256().

I’m a bit surprised that it’s so slow. Maybe, unwinding the loop once may speed up.

Beside, your are doing a ToLower() which iterates on every character and allocates a copy of the string. That’s what’s consuming cpu.

2 Likes

Thank you all for your replies. My goal is indeed to make an even number odd (so if it decrements it by one thats fine). Will try your proposals and come back with my findings

2 Likes

Done. Performance gained significantly. Here’s the new methodC. I opened the capitalized parameter because it needs to know when to switch from 0x9 to 0xA or 0xa if we avoid strings.ToLower(...).

Also, I’m still getting Big.Int inaccuracy after byte manipulations while the hex value is incremented correctly at edge cases. Can someone shed some light?

goos: linux
goarch: amd64
pkg: gosandbox
BenchmarkMethodA-8      26731393                43.3 ns/op
BenchmarkMethodB-8      17746983                67.9 ns/op
BenchmarkMethodC-8      46350786                25.1 ns/op
PASS
ok      gosandbox       3.669s
Code
package main

import (
	"fmt"
	"math/big"
)

const (
	shasum = "8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf73f"
)

func methodC(s *[]byte, capitalized bool) {
	if s == nil {
		return
	}

	length := len(*s)
	index := 0
	for i := 0; i < length; i++ {
		index = length - 1 - i
		x := &(*s)[index : index+1][0]

		switch *x {
		case 0x41, 0x42, 0x43, 0x44, 0x45:
			// A B C D E
			fallthrough
		case 0x61, 0x62, 0x63, 0x64, 0x65:
			// a b c d e
			fallthrough
		case 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38:
			// 0 1 2 3 4 5 6 7 8
			*x += 1
		case 0x39: // 9
			*x = 0x61 // set to a
			if capitalized {
				*x = 0x41 // set to A
			}
		case 0x46, 0x66: // F f
			*x = 0x30
			continue
		default:
			return
		}

		break
	}
}

func methodB(x *big.Int) {
	x.Add(x, big.NewInt(1))
}

func methodA(x *big.Int) {
	x.Not(x)
	x.Neg(x)
}

func main() {
	zz := new(big.Int)

	hash := []byte(shasum)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method A: %s\n", zz.String())
	methodA(zz)
	fmt.Printf("AFTER method A : %s\n", zz.String())

	hash = []byte(shasum)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method B: %s\n", zz.String())
	methodB(zz)
	fmt.Printf("AFTER method B : %s\n", zz.String())

	hash = []byte(shasum)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method C: %s\n", zz.String())
	fmt.Printf("DEBUG BEFORE method C: %s\n", string(hash))
	methodC(&hash, false)
	zz.SetBytes(hash[:])
	fmt.Printf("DEBUG AFTER method C : %s\n", string(hash))
	fmt.Printf("AFTER method C : %s\n", zz.String())
}
// Output:
// BEFORE method A: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154918
// AFTER method A : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154919
// BEFORE method B: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154918
// AFTER method B : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154919
// BEFORE method C: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154918
// DEBUG BEFORE method C: 8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf73f
// DEBUG AFTER method C : 8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf740
// AFTER method C : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721155120
Benchmark Codes
package main

import (
	"math/big"
	"testing"
)

func BenchmarkMethodA(b *testing.B) {
	tgt := new(big.Int)

	for i := 0; i < b.N; i++ {
		hash := []byte(shasum)
		tgt.SetBytes(hash[:])
		methodA(tgt)
	}
}

func BenchmarkMethodB(b *testing.B) {
	tgt := new(big.Int)

	for i := 0; i < b.N; i++ {
		hash := []byte(shasum)
		tgt.SetBytes(hash[:])
		methodB(tgt)
	}
}

func BenchmarkMethodC(b *testing.B) {
	tgt := new(big.Int)

	for i := 0; i < b.N; i++ {
		hash := []byte(shasum)
		methodC(&hash, false)
		tgt.SetBytes(hash[:])
	}
}


What do you mean?

@NobbZ is referring to bit masking if you use XOR gate, which is completely different from increment by 1 in nature.

1 Like

My question was phrased in a wrong way. I don’t need to increment a big number by one, just need to make it even (if it’s odd) or vice-versa.

2 Likes

MethodA works perfectly, thank you!

2 Likes

You might need to re-title the topic (Prefix: retitled - …). All current methods are not masking even/odd numbers, which is your true intention. Give me time to work it out.

1 Like

Here are the new codes for changing odd number to even (methodA) using AND NOT gates. The methodC is modified to match the new requirement.

My recommendation is still methodA because of that big.Int parsing inaccuracy.

goos: linux
goarch: amd64
pkg: gosandbox
BenchmarkMethodA-8      20265528                57.2 ns/op
BenchmarkMethodC-8      56330416                20.8 ns/op
PASS
ok      gosandbox       2.414s
Code
package main

import (
	"fmt"
	"math/big"
)

const (
	shasum = "8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf73f"
)

func methodC(s *[]byte, capitalized bool) {
	if s == nil {
		return
	}

	index := len(*s) - 1
	x := &(*s)[index : index+1][0]

	// character recognitions
	switch *x {
	case 0x31, 0x33, 0x35, 0x37, 0x39, 0x42, 0x44, 0x46, 0x62, 0x64, 0x66:
		// 1 3 5 7 9 B D F b d f
		*x -= 0x01
	case 0x30, 0x32, 0x34, 0x36, 0x38, 0x41, 0x43, 0x45, 0x61, 0x63, 0x65:
		// 0 2 4 6 8 A C E a c e
		// do nothing
	default:
		return
	}
}

func methodA(x *big.Int) {
	x.AndNot(x, big.NewInt(1))
}

func main() {
	zz := new(big.Int)

	hash := []byte(shasum)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method A: %s\n", zz.String())
	methodA(zz)
	fmt.Printf("AFTER method A : %s\n", zz.String())

	hash = []byte(shasum)
	zz.SetBytes(hash[:])
	fmt.Printf("BEFORE method C: %s\n", zz.String())
	fmt.Printf("DEBUG BEFORE method C: %s\n", string(hash))
	methodC(&hash, false)
	zz.SetBytes(hash[:])
	fmt.Printf("DEBUG AFTER method C : %s\n", string(hash))
	fmt.Printf("AFTER method C : %s\n", zz.String())
}
// Output:
// BEFORE method A: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154918
// AFTER method A : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154918
// BEFORE method C: 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154918
// DEBUG BEFORE method C: 8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf73f
// DEBUG AFTER method C : 8c32eeb180c961c5015ed69a1579e6ad98479c9509e5c524f096cdda5e1cf73e
// AFTER method C : 2953253003934257607559289743915026435532263105800530010414720734192461358425063874354789587599756988242021836199015574276107182587110732205759776721154917

Benchmark Codes
package main

import (
	"math/big"
	"testing"
)

func BenchmarkMethodA(b *testing.B) {
	tgt := new(big.Int)

	for i := 0; i < b.N; i++ {
		hash := []byte(shasum)
		tgt.SetBytes(hash[:])
		methodA(tgt)
	}
}

func BenchmarkMethodC(b *testing.B) {
	tgt := new(big.Int)

	for i := 0; i < b.N; i++ {
		hash := []byte(shasum)
		methodC(&hash, false)
		tgt.SetBytes(hash[:])
	}
}
2 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.