' Large Fibonacci — computes Fibonacci numbers using string-based big integers
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL fibA AS STRING
    LOCAL fibB AS STRING
    LOCAL fibC AS STRING
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL n AS LONG
    LOCAL carry AS LONG
    LOCAL digitSum AS LONG
    LOCAL digitA AS LONG
    LOCAL digitB AS LONG
    LOCAL maxLen AS LONG
    LOCAL resultStr AS STRING
    LOCAL digitChar AS STRING
    LOCAL lineStr AS STRING
    LOCAL paddedA AS STRING
    LOCAL paddedB AS STRING
    LOCAL chA AS STRING
    LOCAL chB AS STRING
    LOCAL fibCount AS LONG
    LOCAL totalDigits AS LONG
    LOCAL digitStr AS STRING
    PRINT "============================================"
    PRINT "     LARGE FIBONACCI NUMBERS (string bigint)"
    PRINT "============================================"
    PRINT ""
    PRINT "Fibonacci sequence using string arithmetic"
    PRINT ""
    PRINT "First 50 Fibonacci numbers:"
    PRINT ""
    fibA = "0"
    fibB = "1"
    PRINT "F(0) = " + fibA
    PRINT "F(1) = " + fibB
    FOR n = 2 TO 50
        IF LEN(fibA) > LEN(fibB) THEN
            maxLen = LEN(fibA)
        ELSE
            maxLen = LEN(fibB)
        END IF
        paddedA = fibA
        paddedB = fibB
        DO WHILE LEN(paddedA) < maxLen
            paddedA = "0" + paddedA
        LOOP
        DO WHILE LEN(paddedB) < maxLen
            paddedB = "0" + paddedB
        LOOP
        carry = 0
        fibC = ""
        FOR i = maxLen TO 1 STEP -1
            chA = MID$(paddedA, i, 1)
            chB = MID$(paddedB, i, 1)
            digitA = ASC(chA) - 48
            digitB = ASC(chB) - 48
            digitSum = digitA + digitB + carry
            IF digitSum >= 10 THEN
                carry = 1
                digitSum = digitSum - 10
            ELSE
                carry = 0
            END IF
            digitChar = CHR$(digitSum + 48)
            fibC = digitChar + fibC
        NEXT i
        IF carry > 0 THEN
            fibC = "1" + fibC
        END IF
        PRINT "F(" + STR$(n) + ") = " + fibC
        fibA = fibB
        fibB = fibC
    NEXT n
    PRINT ""
    PRINT "============================================"
    PRINT "     LARGE FIBONACCI (100th number)"
    PRINT "============================================"
    PRINT ""
    fibA = "0"
    fibB = "1"
    FOR n = 2 TO 100
        IF LEN(fibA) > LEN(fibB) THEN
            maxLen = LEN(fibA)
        ELSE
            maxLen = LEN(fibB)
        END IF
        paddedA = fibA
        paddedB = fibB
        DO WHILE LEN(paddedA) < maxLen
            paddedA = "0" + paddedA
        LOOP
        DO WHILE LEN(paddedB) < maxLen
            paddedB = "0" + paddedB
        LOOP
        carry = 0
        fibC = ""
        FOR i = maxLen TO 1 STEP -1
            chA = MID$(paddedA, i, 1)
            chB = MID$(paddedB, i, 1)
            digitA = ASC(chA) - 48
            digitB = ASC(chB) - 48
            digitSum = digitA + digitB + carry
            IF digitSum >= 10 THEN
                carry = 1
                digitSum = digitSum - 10
            ELSE
                carry = 0
            END IF
            digitChar = CHR$(digitSum + 48)
            fibC = digitChar + fibC
        NEXT i
        IF carry > 0 THEN
            fibC = "1" + fibC
        END IF
        fibA = fibB
        fibB = fibC
    NEXT n
    totalDigits = LEN(fibC)
    PRINT "F(100) has " + STR$(totalDigits) + " digits"
    PRINT "F(100) = " + fibC
    PRINT ""
    PRINT "============================================"
    PRINT "     FIBONACCI DIGIT COUNTS"
    PRINT "============================================"
    PRINT ""
    fibA = "0"
    fibB = "1"
    PRINT "n     digits"
    FOR n = 1 TO 200
        IF LEN(fibA) > LEN(fibB) THEN
            maxLen = LEN(fibA)
        ELSE
            maxLen = LEN(fibB)
        END IF
        paddedA = fibA
        paddedB = fibB
        DO WHILE LEN(paddedA) < maxLen
            paddedA = "0" + paddedA
        LOOP
        DO WHILE LEN(paddedB) < maxLen
            paddedB = "0" + paddedB
        LOOP
        carry = 0
        fibC = ""
        FOR i = maxLen TO 1 STEP -1
            chA = MID$(paddedA, i, 1)
            chB = MID$(paddedB, i, 1)
            digitA = ASC(chA) - 48
            digitB = ASC(chB) - 48
            digitSum = digitA + digitB + carry
            IF digitSum >= 10 THEN
                carry = 1
                digitSum = digitSum - 10
            ELSE
                carry = 0
            END IF
            digitChar = CHR$(digitSum + 48)
            fibC = digitChar + fibC
        NEXT i
        IF carry > 0 THEN
            fibC = "1" + fibC
        END IF
        IF n MOD 10 = 0 OR n = 1 THEN
            digitStr = STR$(LEN(fibC))
            DO WHILE LEN(digitStr) < 6
                digitStr = " " + digitStr
            LOOP
            PRINT "F(" + STR$(n) + ")" + digitStr
        END IF
        fibA = fibB
        fibB = fibC
    NEXT n
    PRINT ""
    PRINT "============================================"
    PRINT "     FIBONACCI WITHOUT STRING (LONG limit)"
    PRINT "============================================"
    PRINT ""
    LOCAL flimit AS LONG
    LOCAL f1 AS LONG
    LOCAL f2 AS LONG
    LOCAL f3 AS LONG
    f1 = 0
    f2 = 1
    flimit = 50
    PRINT "Fibonacci (LONG) up to F(" + STR$(flimit) + "):"
    PRINT ""
    lineStr = ""
    FOR n = 0 TO flimit
        IF n = 0 THEN
            f3 = 0
        ELSE
            IF n = 1 THEN
                f3 = 1
            ELSE
                f3 = f1 + f2
                f1 = f2
                f2 = f3
            END IF
        END IF
        digitStr = STR$(f3)
        DO WHILE LEN(digitStr) < 8
            digitStr = " " + digitStr
        LOOP
        lineStr = lineStr + "F(" + STR$(n) + ")" + digitStr + " "
        IF (n + 1) MOD 4 = 0 THEN
            PRINT lineStr
            lineStr = ""
        END IF
    NEXT n
    IF lineStr <> "" THEN
        PRINT lineStr
    END IF
    PRINT ""
    PRINT "Done"
    FUNCTION = 0
END FUNCTION
