There are 2 parts I want to address out:
1st Part: Back to Topic
-
To OP @Gowtham_Girithar, choose the one that makes sense and can explain from your side. After optimizing and benchmark some algorithms, here are the best codes between byMath and byByte I can come out with. Both approaches are making sense; the only things left are whether it fulfills the objective (question requirement) and how do you understand the algorithm (one is by mathematics, one is by text encoding).
-
I’m hiding the code just in case you want to try things out yourself. View it by clicking on the hiding block.
-
There is a benchmark result inside for you to visualize the performance and judge from there using my current system. Performance results are nonsense by its own without running it against a hypothesis the benchmark on your system and compare. That’s why I would avoid the topic for that.
-
Negative numbers and positive numbers approaches are solely depends on you. From your topic, your positive number is inserted when the RHS is lower than the subject. Hence, the code’s insertion is based on that assumption. If that’s your algorithm, then negative number is the opposite (mainly because negative number is always lower than positive number on number point system). Again, since you did not specify, decision is upto yours. Currently, I’m commenting out negSign in case you need it.
-
For exploration, do explore into math package like @Ethindp pointed . You will know why I came out from there later. For simple problem as such, you do not need to get yourself into floating-point data type.
-
When I say complicated division, I meant by the divisor requires complex math like log, exponent, etc like
Code
package main
import (
"fmt"
"strconv"
)
const (
target = 8234
subject = 2
)
func byMath(t int, s uint) string {
// negSign := false
// guard negative number
if t < 0 {
t *= -1
//negSign = true
}
// guard against 0-9
if s > 9 {
panic("s should be digit from 0-9. Fix me before compile.\n")
}
base := 10
div := 1
v := []int{}
for {
r := (t / div) % base
if r == 0 {
break
}
v = append([]int{r}, v...)
div *= base
}
out := ""
inserted := false
for _, d := range v {
if d <= int(s) && !inserted {
out += strconv.Itoa(int(s))
inserted = true
}
out += strconv.Itoa(d)
}
return out
}
func byByte(t int, s uint) string {
var v []byte
var x byte
// negSign := false
// guard negative number
if t < 0 {
t *= -1
//negSign = true
}
// guard against 0-9
if s > 9 {
panic("s should be digit from 0-9. Fix me before compile.\n")
}
v = []byte(strconv.Itoa(t))
x = []byte(strconv.Itoa(int(s)))[0]
p := 0
l := len(v)
for i := range v {
if i == l-1 {
p = 1
break
}
if v[i] <= x {
break
}
p++
}
out := append(v[:p], append([]byte{x}, v[p:]...)...)
return string(out)
}
func main() {
fmt.Printf("byMath: %v\n", byMath(target, subject))
fmt.Printf("byByte: %v\n", byByte(target, subject))
}
Output:
Output:
byMath: 82234
byByte: 82234
Benchmark:
goos: linux
goarch: amd64
pkg: gosandbox
BenchmarkByMath-8 2915108 449 ns/op
BenchmarkByBytes-8 12081392 100 ns/op
PASS
ok gosandbox 3.043s
Bechmark Codes
package main
import (
"testing"
)
var result string
func BenchmarkByMath(b *testing.B) {
var r string
for n := 0; n < b.N; n++ {
r = byMath(n, 2)
}
result = r
}
func BenchmarkByBytes(b *testing.B) {
var r string
for n := 0; n < b.N; n++ {
r = byByte(n, 2)
}
result = r
}
The 2nd Part: Ethin Probst Division Arguments
1. the Keyword “Complicated”
There are 2 kinds of “complicated” perceptions here. From @Ethindp perceptive, it’s about more codes. From my perspective, it’s about readable, and maintainable codes that does not hide things. Hence, it’s a matter of point of views (and preference).
I prioritizes solving problem first, performance later. The rationale for me is simple: I’m not interested in getting into highway to hell; I would make sure the direction is correct before proceeding even as slow as country road.
2. Argument about Division
Mathematically, it is proven that division requires more efforts to reach result. This is the only reason why division has a single rule “not to divide by 0” and the result is not infinity but an error/not-a-number.
This is one simple program that benchmark all basic mathematical operations on Go compiler:
package main
import (
"fmt"
)
const (
subject = 10
target = 2
)
func divideQAndR(x, y int) (r1 int, r2 int) {
r1 = x / y
r2 = x % y
return r1, r2
}
func divideRemainderOnly(x, y int) (r1 int, r2 int) {
r1 = x % y
return r1, r2
}
func divideQuotientOnly(x, y int) (r1 int, r2 int) {
r1 = x / y
return r1, r2
}
func multiply(x, y int) (r1 int, r2 int) {
r1 = x * y
return r1, r2
}
func subtract(x, y int) (r1 int, r2 int) {
r1 = x - y
return r1, r2
}
func add(x, y int) (r1 int, r2 int) {
r1 = x + y
return r1, r2
}
func main() {
r1, r2 := add(subject, target)
fmt.Printf("Add R1:%v R2:%v \n", r1, r2)
r1, r2 = subtract(subject, target)
fmt.Printf("Subtract R1:%v R2:%v \n", r1, r2)
r1, r2 = multiply(subject, target)
fmt.Printf("Multiply R1:%v R2:%v \n", r1, r2)
r1, r2 = divideRemainderOnly(subject, target)
fmt.Printf("DivideRemainderOnly R1:%v R2:%v \n", r1, r2)
r1, r2 = divideQuotientOnly(subject, target)
fmt.Printf("DivideQuotientOnly R1:%v R2:%v \n", r1, r2)
r1, r2 = divideQAndR(subject, target)
fmt.Printf("DivideQAndR R1:%v R2:%v \n", r1, r2)
}
OUTPUT:
// goos: linux
// goarch: amd64
// pkg: gosandbox/math
// BenchmarkAdd-8 1000000000 0.378 ns/op
// BenchmarkSubtract-8 1000000000 0.394 ns/op
// BenchmarkMultiply-8 1000000000 0.447 ns/op
// BenchmarkDivideQuotientOnly-8 1000000000 0.565 ns/op
// BenchmarkDivideRemainderOnly-8 1000000000 0.738 ns/op
// BenchmarkDivideQandR-8 1000000000 0.826 ns/op
// PASS
// ok gosandbox/math 3.698s
Benchmark Codes
package main
import (
"testing"
)
var result1 int
var result2 int
func BenchmarkAdd(b *testing.B) {
var r1, r2 int
for n := 0; n < b.N; n++ {
r1, r2 = add(n, target)
}
result1 = r1
result2 = r2
}
func BenchmarkSubtract(b *testing.B) {
var r1, r2 int
for n := 0; n < b.N; n++ {
r1, r2 = subtract(n, target)
}
result1 = r1
result2 = r2
}
func BenchmarkMultiply(b *testing.B) {
var r1, r2 int
for n := 0; n < b.N; n++ {
r1, r2 = multiply(n, target)
}
result1 = r1
result2 = r2
}
func BenchmarkDivideQuotientOnly(b *testing.B) {
var r1, r2 int
for n := 0; n < b.N; n++ {
r1, r2 = divideQuotientOnly(n, target)
}
result1 = r1
result2 = r2
}
func BenchmarkDivideRemainderOnly(b *testing.B) {
var r1, r2 int
for n := 0; n < b.N; n++ {
r1, r2 = divideRemainderOnly(n, target)
}
result1 = r1
result2 = r2
}
func BenchmarkDivideQandR(b *testing.B) {
var r1, r2 int
for n := 0; n < b.N; n++ {
r1, r2 = divideQAndR(n, target)
}
result1 = r1
result2 = r2
}
See the CPU rate differences between each operations using only Go compiler? This is not some backward Pentinum 4 (486) CPU, this is on i7 CPU.
However, choosing whether to divide or to multiply, if given a choice (like you still able to simplify your mathematical model or explore another formulation) and your CPU does show division has high cost, you can go for multiplication. Otherwise, use divide as it is part of the requirement and save time and efforts.
One example of math model alteration (exponent base conversion):
B^y = E^x
y*logB(B) = x*logB(E)
y*(1) = x*logB(E)
y = x*logB(E) --- [1]
OR
B^y = E^x
y*logE(B) = x*logE(E)
y*logE(B) = x*(1)
y = x / logE(B) --- [2]
y = 5 / (2 + x) --- [3]
In this case, [1] is favored over [2] when having a choice based on the operations data comparison above.
However, for case [3], it makes not sense to further simplify it to multiplication since it complicates things. Therefore, use the divide instead.
@Ethindp has a point about my paranoid over division: all the explanations here, as far as the modern processor goes (e.g. MHz to GHz), even in my point-of-view, should be considered as premature optimization but be aware of it. I can clarify that I’m an old timer that approach things bottom up, and made some hiccup here and there in the past, thus the built-up sensitivity towards division.
However as I iterate again: DO NOT get religious about “you should not using divide at all”. Solve the problem first the way you understand. Performance optimization always come in later, after you solve the problem. Changing math from division to multiplication is a kind of optimization.
3. The Need Of Maintaining Int Data Types
Back to the question, as far as I understand current question (unless OP did not mention the details out), it’s about the comparing 2 digits (finite values: 0 to 9) and the need to disassemble number into a digit slice then reassemble back.
There is no requirement for addition/subtraction/multiplication/divide of any digits except logical comparison (less than or equal) either from left-hand-side first or right-hand-side. If OP wants this, then it makes no sense to even get into string.
That’s why I’m on the byte side. It’s not complicated and algorithmic-ally, it makes a lot of visual sense. The best part about it is that the byte representations still maintains its mathematics properties for comparison purpose.
It also does not means that it can’t be done mathematically. It can. See above, and the benchmark difference, the requirements, and make your own judgement from there.
Peace.
