Divison.fs

open System

let div (a:int) (b:int) =
    if b = 0 then raise (new DivideByZeroException())
    let aa, ab = uint32(Math.Abs(a)), uint32(Math.Abs(b))
    if aa < ab then 0 else
        let rec search ab v =
            if ab > aa then ab >>> 1, v >>> 1 else search (ab <<< 1) (v <<< 1)
        let ab, v = search ab 1u
        let rec div ret aa ab v =
            if v = 0u then int(ret) else
                let ret, aa = if aa >= ab then ret + v, aa - ab else ret, aa
                div ret aa (ab >>> 1) (v >>> 1)
        let aret = div 0u aa ab v
        if Math.Sign(a) = Math.Sign(b) then aret else -aret

let mod' (a:int) (b:int) =
    if b = 0 then raise (new DivideByZeroException())
    let aa, ab = uint32(Math.Abs(a)), uint32(Math.Abs(b))
    let aret =
        if aa < ab then int(aa) else
            let rec search ab =
                if ab > aa then ab >>> 1 else search (ab <<< 1)
            let ab2 = search ab
            let rec mod' aa ab2 =
                let aa = if aa >= ab2 then aa - ab2 else aa
                if ab = ab2 then int(aa) else mod' aa (ab2 >>> 1)
            mod' aa ab2
    if Math.Sign(a) = Math.Sign(b) then aret else -aret

let divmod (a:int) (b:int) =
    if b = 0 then raise (new DivideByZeroException())
    let aa, ab = uint32(Math.Abs(a)), uint32(Math.Abs(b))
    let ar1, ar2 =
        if aa < ab then 0, int(aa) else
            let rec search ab v =
                if ab > aa then ab >>> 1, v >>> 1 else search (ab <<< 1) (v <<< 1)
            let ab, v = search ab 1u
            let rec divmod ret aa ab v =
                if v = 0u then int(ret), int(aa) else
                    let ret, aa = if aa >= ab then ret + v, aa - ab else ret, aa
                    divmod ret aa (ab >>> 1) (v >>> 1)
            divmod 0u aa ab v
    if Math.Sign(a) = Math.Sign(b) then ar1, ar2 else -ar1, -ar2

let r = new Random()
for i = 1 to 10 do
    let a, b = r.Next(), r.Next() &&& 0xffff
    printfn "%d / %d = %d ... %d (%d ... %d) %A" a b (a / b) (a % b) (div a b) (mod' a b) (divmod a b)