Devise an algorithm to determine the square root of a base 2 positive integer without expressing it in base 10.

I first tried to look for a pattern recognition method but could not see anything helpful.
In python, I found that trying to work with binary numbers of the format 0b1101 for example would give results in decimal.  So to stay completely away from decimal I decided to just work with strings of 1s and 0s.  This resulted in needing to write routines to do subtraction and comparison of two binary strings.
No routine was needed for multiplication because the only multiplication needed in this algorithm is by 2 (just concatenate a 0 at the end) or by 1.

The algorithm is simply the long division form of taking square roots, but translated to binary.
I did get a working program.  The first parameter is the binary string, the second parameter is how many decimal places (binary places?) of precision you want.  If you omit the second parameter, it defaults to zero, a binary integer.  Any "remainder" is truncated.



def binCompare(a,b):
    """ bool test if a < or = or > b, where a and b are strings of 1s and 0s representing binary numbers.  a>b: 1, a<b: -1, a=b: 0    """
    a = a.lstrip('0')
    b = b.lstrip('0')
    if a == '':
        a = '0'
    if b == '':
        b = '0'
    if len(a) > len(b):
        return 1
    elif len(a) < len(b):
        return -1
    else:
        for i  in range(len(a)):
            if a[i] == b[i]:
                continue
            if a[i] < b[i]:
                return -1
            if a[i] > b[i]:
                return 1
    return 0

def binSubtract(a,b):
    """ return a-b where a and be are string variables representing binary numbers  """
    a = a.lstrip('0')
    b = b.lstrip('0')
    if a == '':
        a = '0'
    if b == '':
        b = '0'
    isMinusSign = ''  #text for minus sign or not
    if b == a:
        return '0'
    elif binCompare(a,b) < 0:    # less than
        isMinusSign = '-'
        cL=a
        aL=b
        bL=cL
    b = '0'*(len(a)-len(b)) + b
    aL = [int(i) for i in a]
    bL = [int(i) for i in b]
    answer = []
    for i in range(len(aL)-1,-1,-1):
        if aL[i] < bL[i]:
            digit = 1
            for j in range(i-1,-1,-1):
                if aL[j] == 1:
                    aL[j] = 0
                    break
                if aL[j] == 0:
                    aL[j] = 1
                
        else:
            digit = aL[i] - bL[i]
        answer.append(digit)
        if isMinusSign == '-':
            print('there is a minus sign in binSubtract',a,b)
    return isMinusSign + (''.join(str(i) for i in answer[::-1])).lstrip('0')

def sqrtBase2(aString, places=0):
    """ aString is a binary number in string format
    places is the number of decimal place precision (defaults to 0)
    output is the binary version of the radicand root """
    aString = aString + '0'*2*places
    length = len(aString)

    if length%2 == 1:
        radicand = [aString[0]] + [aString[i:i+2] for i in range(1,length,2)  ]
    else:
        radicand = [aString[i:i+2] for i in range(0,length,2)  ]
    root = diff = sub = divisor = ''

    for i in range(len(radicand)):
        dividend = diff + radicand[i]
        divisor = root + '0'    # multiplies by 2
        if binCompare(divisor + '1', dividend) < 1:
            sub = divisor + '1'
            root = root + '1'
            diff = binSubtract(dividend,sub)
        else:
            sub = '0'
            root = root + '0'
            diff = dividend
    return root[:len(root) - places] + '.' + root[-places:]

Posted by Larry on 2023-03-05 06:58:23