' Fixed-Point Square Root — integer square root using Newton's method
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL n AS LONG
    LOCAL x AS LONG
    LOCAL guess AS LONG
    LOCAL prevGuess AS LONG
    LOCAL iter AS LONG
    LOCAL maxIter AS LONG
    LOCAL result AS LONG
    LOCAL remainder AS LONG
    LOCAL testVal AS LONG
    LOCAL digits AS LONG
    LOCAL precision AS LONG
    LOCAL i AS LONG
    LOCAL scaledVal AS LONG
    LOCAL intPart AS LONG
    LOCAL fracPart AS LONG
    LOCAL temp AS LONG
    LOCAL errorVal AS LONG
    LOCAL success AS LONG
    LOCAL totalTests AS LONG
    LOCAL passedTests AS LONG
    LOCAL failedTests AS LONG
    LOCAL lineStr AS STRING
    maxIter = 50
    totalTests = 0
    passedTests = 0
    failedTests = 0
    PRINT "============================================"
    PRINT "     FIXED-POINT SQUARE ROOT CALCULATOR"
    PRINT "============================================"
    PRINT ""
    PRINT "Integer square root using Newton's method"
    PRINT ""
    FOR testVal = 0 TO 100
        n = testVal
        IF n = 0 THEN
            result = 0
        ELSE
            guess = n
            IF guess > 65535 THEN
                guess = 65535
            END IF
            IF guess < 1 THEN
                guess = 1
            END IF
            prevGuess = 0
            FOR iter = 1 TO maxIter
                IF guess = 0 THEN
                    guess = 1
                END IF
                prevGuess = guess
                guess = (guess + n / guess) / 2
                IF guess = prevGuess THEN
                    EXIT FOR
                END IF
                errorVal = guess - prevGuess
                IF errorVal < 0 THEN
                    errorVal = 0 - errorVal
                END IF
                IF errorVal < 1 THEN
                    EXIT FOR
                END IF
            NEXT iter
            result = guess
        END IF
        IF result * result > n THEN
            result = result - 1
        END IF
        lineStr = "sqrt(" + STR$(n) + ") = " + STR$(result)
        IF n > 999 THEN
            digits = 0
        ELSE
            digits = 0
        END IF
        PRINT lineStr
    NEXT testVal
    PRINT ""
    PRINT "Testing large values"
    PRINT ""
    FOR i = 0 TO 5
        n = 10000 * (i + 1) * (i + 1)
        IF n = 0 THEN
            result = 0
        ELSE
            guess = n
            IF guess > 65535 THEN
                guess = 65535
            END IF
            IF guess < 1 THEN
                guess = 1
            END IF
            prevGuess = 0
            FOR iter = 1 TO maxIter
                IF guess = 0 THEN
                    guess = 1
                END IF
                prevGuess = guess
                guess = (guess + n / guess) / 2
                IF guess = prevGuess THEN
                    EXIT FOR
                END IF
                errorVal = guess - prevGuess
                IF errorVal < 0 THEN
                    errorVal = 0 - errorVal
                END IF
                IF errorVal < 1 THEN
                    EXIT FOR
                END IF
            NEXT iter
            result = guess
        END IF
        IF result * result > n THEN
            result = result - 1
        END IF
        PRINT "sqrt(" + STR$(n) + ") = " + STR$(result)
        totalTests = totalTests + 1
        IF result * result <= n AND (result + 1) * (result + 1) > n THEN
            passedTests = passedTests + 1
        ELSE
            failedTests = failedTests + 1
        END IF
    NEXT i
    PRINT ""
    PRINT "Precision square root with scaled integer arithmetic"
    PRINT ""
    FOR n = 0 TO 20
        precision = 1000
        scaledVal = n * precision * precision
        IF scaledVal = 0 THEN
            intPart = 0
            fracPart = 0
        ELSE
            guess = scaledVal
            IF guess > 65535 THEN
                guess = 65535
            END IF
            IF guess < 1 THEN
                guess = 1
            END IF
            prevGuess = 0
            FOR iter = 1 TO maxIter
                IF guess = 0 THEN
                    guess = 1
                END IF
                prevGuess = guess
                guess = (guess + scaledVal / guess) / 2
                IF guess = prevGuess THEN
                    EXIT FOR
                END IF
                errorVal = guess - prevGuess
                IF errorVal < 0 THEN
                    errorVal = 0 - errorVal
                END IF
                IF errorVal < 1 THEN
                    EXIT FOR
                END IF
            NEXT iter
            result = guess
            IF result * result > scaledVal THEN
                result = result - 1
            END IF
            intPart = result / precision
            fracPart = result - intPart * precision
        END IF
        PRINT "sqrt(" + STR$(n) + ") = " + STR$(intPart) + "." + STR$(fracPart)
    NEXT n
    PRINT ""
    PRINT "Checking perfect squares"
    PRINT ""
    FOR i = 0 TO 30
        n = i * i
        IF n = 0 THEN
            result = 0
        ELSE
            guess = n
            IF guess > 65535 THEN
                guess = 65535
            END IF
            IF guess < 1 THEN
                guess = 1
            END IF
            prevGuess = 0
            FOR iter = 1 TO maxIter
                IF guess = 0 THEN
                    guess = 1
                END IF
                prevGuess = guess
                guess = (guess + n / guess) / 2
                IF guess = prevGuess THEN
                    EXIT FOR
                END IF
                errorVal = guess - prevGuess
                IF errorVal < 0 THEN
                    errorVal = 0 - errorVal
                END IF
                IF errorVal < 1 THEN
                    EXIT FOR
                END IF
            NEXT iter
            result = guess
        END IF
        IF result * result > n THEN
            result = result - 1
        END IF
        totalTests = totalTests + 1
        IF result = i THEN
            passedTests = passedTests + 1
        ELSE
            failedTests = failedTests + 1
        END IF
        PRINT "sqrt(" + STR$(n) + ") = " + STR$(result) + " (expected " + STR$(i) + ")"
    NEXT i
    PRINT ""
    PRINT "Summary: " + STR$(passedTests) + " passed, " + STR$(failedTests) + " failed"
    FUNCTION = 0
END FUNCTION
