CODEWITHSUNDEEP
algorithmmathgo
Nan Xiao
Nan Xiao

Reputation: 17477

How to get the quotient and remainder effectively without using "/" and "%"?

I have implemented a simple function which returns the quotient and remainder when the divisor is the power of 10: 

func getQuotientAndRemainder(num int64, digits uint) (int64, int64) {
    divisor := int64(math.Pow(10, float64(digits)))
    if num >= divisor {
        return num / divisor, num % divisor
    } else {
        return 0, num
    }
}

Just curious, except using directly / and % operators, is there any better algorithm to get the the quotient and remainder? Or only in the case when the divisor is the power of 10?

Upvotes: 0

Views: 277

Answers (2)

peterSO
peterSO

Reputation: 166704

Obviously, you should run some Go benchmarks: Benchmarks, Package testing.

Your solution doesn't look very efficient. Try this:

package main

import "fmt"

func pow(base, exp int64) int64 {
    p := int64(1)
    for exp > 0 {
        if exp&1 != 0 {
            p *= base
        }
        exp >>= 1
        base *= base
    }
    return p
}

func divPow(n, base, exp int64) (q int64, r int64) {
    p := pow(base, exp)
    q = n / p
    r = n - q*p
    return q, r
}

func main() {
    fmt.Println(divPow(42, 10, 1))
    fmt.Println(divPow(-42, 10, 1))
}

Output:

4 2
-4 -2

Benchmark:

BenchmarkDivPow                     20000000            77.4 ns/op
BenchmarkGetQuotientAndRemainder     5000000           296 ns/op

Upvotes: 1

thwd
thwd

Reputation: 24848

return num / divisor, num % divisor

The "algorithm" is sound and written in arguably the best way possible: expressively. If anything, this part of your code may be overly complicated:

int64(math.Pow(10, float64(digits)))

Converting to and from float64 is arguably sub-optimal. Also, 10 to the power of anything greater than 18 will overflow int64. I suggest you add a sanity check and replace the code with a multiplying loop and measure its performance.

But then: if performance is your concern, just implement it in assembly.

Upvotes: 1

Related Questions