Pergunta

As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary.

I'm sure this is not original; can anyone provide a reference?

// All arithmetic is truncating unsigned integer arithmetic
// Actual implementation uses bit shifts
// Indention level defines statement scope

def sqrt(r)                         // r is an unsigned integer
    residue = r                     // residue will be the 'remainder'
    root = 0                        // root will be the integer square root (floor(r**0.5))
    onebit = 2**(bitlength(r)-2)    // onebit is a moving 'bitpicker'
    while onebit > r                
        onebit = onebit / 4         // find highest bitpicker less than r
    while onebit > 0 
        x = root + onebit           // Current root plus onebit
        if residue >= x             // Room to subtract?
            residue = residue - x   // Yes - deduct from residue
            root = x + onebit       // and step root
        root = root / 2             // Slide evolving root 1 bit down the residue
        onebit = onebit / 4         // Slide the bitpick 1 bit down the root
    assert(root**2 + residue == r)
    assert((root+1)**2 > r)
    return root, residue

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top