Vedic Division: Nikhilam and Paravartya Sutras

def nikhilam_divide(dividend, divisor):
    """Fast division for divisors near a power of 10."""
    # Find base and deviation
    base = 10 ** len(str(divisor))
    deviation = base - divisor
    
    result_q = 0
    remaining = dividend
    
    for _ in range(20):
        prefix = remaining // base
        suffix = remaining % base
        
        if prefix == 0:
            break
        
        result_q += prefix
        remaining = suffix + prefix * deviation
    
    # Final adjustment
    while remaining >= divisor:
        remaining -= divisor
        result_q += 1
    
    return result_q, remaining

tests = [(1458, 9), (1032, 97), (15234, 998), (5000, 96)]
for d, div in tests:
    q, r = nikhilam_divide(d, div)
    eq, er = divmod(d, div)
    ok = "✓" if (q == eq and r == er) else "✗"
    print(f"{d} ÷ {div} = {q} R {r} {ok}")

def paravartya_divide(dividend, divisor):
    """Paravartya division for general divisors."""
    divisor_str = str(divisor)
    n = len(divisor_str)
    principal = int(divisor_str[0])
    
    # Transposed digits (negative of remaining digits)
    transposed = [-int(d) for d in divisor_str[1:]]
    
    dividend_str = str(dividend)
    # Pad dividend to have at least n digits
    work = [int(d) for d in dividend_str]
    
    quotient = []
    
    for i in range(len(work) - (n - 1)):
        if i >= len(work):
            break
        
        q_digit = work[i]
        quotient.append(q_digit)
        
        # If quotient digit is 0, skip multiplication
        if q_digit == 0:
            continue
        
        # Multiply transposed digits and add to next positions
        for j, t in enumerate(transposed):
            if i + j + 1 < len(work):
                work[i + j + 1] += q_digit * t
    
    # The remainder is the last (n-1) digits of work
    remainder_digits = work[-(n-1):] if n > 1 else [work[-1]]
    
    # Convert remainder to positive if needed
    for i in range(len(remainder_digits) - 1, -1, -1):
        if remainder_digits[i] < 0:
            borrow = (-remainder_digits[i] + 9) // 10
            remainder_digits[i] += borrow * 10
            if i > 0:
                remainder_digits[i-1] -= borrow
    
    q = int(''.join(str(d) if d >= 0 else '0' for d in quotient)) if quotient else 0
    r = 0
    for d in remainder_digits:
        r = r * 10 + max(0, d)
    
    # Handle cases where remainder >= divisor
    while r >= divisor:
        r -= divisor
        q += 1
    
    return q, r

tests = [(1356, 123), (4821, 211), (10345, 112)]
for d, div in tests:
    q, r = paravartya_divide(d, div)
    eq, er = divmod(d, div)
    ok = "✓" if (q == eq and r == er) else "✗"
    print(f"{d} ÷ {div} = {q} R {r} {ok}")

def vedic_divisibility_test(num, divisor):
    """Check divisibility using Vedic methods."""
    tests = {
        9: lambda n: sum(int(d) for d in str(n)) % 9 == 0,
        11: lambda n: abs(sum(int(d) for i, d in enumerate(str(n)) if i % 2 == 0) - 
                          sum(int(d) for i, d in enumerate(str(n)) if i % 2 == 1)) % 11 == 0,
    }
    
    if divisor == 13:
        n = num
        while n > 99:
            last = n % 10
            n = n // 10 + last * 4
        return n % 13 == 0
    elif divisor == 17:
        n = num
        while n > 99:
            last = n % 10
            n = n // 10 - last * 5
        return n % 17 == 0
    elif divisor == 19:
        n = num
        while n > 99:
            last = n % 10
            n = n // 10 + last * 2
        return n % 19 == 0
    elif divisor in tests:
        return tests[divisor](num)
    else:
        return num % divisor == 0

for num, div in [(1458, 9), (121, 11), (169, 13), (289, 17), (361, 19)]:
    result = vedic_divisibility_test(num, div)
    print(f"{num} divisible by {div}? {result}")

def nikhilam_decimal(dividend, divisor, decimal_places=5):
    """Get decimal expansion using Nikhilam principles."""
    q, r = nikhilam_divide(dividend, divisor)
    result = f"{q}."
    
    for _ in range(decimal_places):
        r *= 10
        digit, r = nikhilam_divide(r, divisor)
        result += str(digit)
        if r == 0:
            break
    
    return result

tests = [(1, 7), (1, 19), (22, 7)]
for d, div in tests:
    res = nikhilam_decimal(d, div, 8)
    print(f"{d}/{div} = {res}")

import time

def traditional_divide(dividend, divisor):
    return divmod(dividend, divisor)

def benchmark():
    test_cases = [
        (1032, 97),
        (15234, 998),
        (450000, 9985),
        (1234567, 9992),
    ]
    
    print(f"{'Problem':<18} {'Vedic (μs)':<12} {'Standard (μs)':<14} {'Speedup':<10}")
    print("-" * 54)
    
    for dividend, divisor in test_cases:
        # Warm up
        for _ in range(1000):
            nikhilam_divide(dividend, divisor)
            traditional_divide(dividend, divisor)
        
        # Benchmark
        start = time.perf_counter()
        for _ in range(10000):
            nikhilam_divide(dividend, divisor)
        vedic_time = (time.perf_counter() - start) * 1e6 / 10000
        
        start = time.perf_counter()
        for _ in range(10000):
            traditional_divide(dividend, divisor)
        std_time = (time.perf_counter() - start) * 1e6 / 10000
        
        speedup = std_time / vedic_time
        print(f"{dividend}÷{divisor:<5} {vedic_time:<12.2f} {std_time:<14.2f} {speedup:<10.2f}x")

benchmark()

def recommend_method(divisor):
    """Recommend the best Vedic division method for a given divisor."""
    base = 10 ** len(str(divisor))
    deviation = base - divisor
    deviation_ratio = deviation / base
    
    if abs(deviation_ratio) < 0.2:
        return "Nikhilam (near base)"
    elif str(divisor)[0] == '1':
        return "Paravartya Yojayet (transpose)"
    elif divisor < 20:
        return "Nikhilam (small divisor)"
    else:
        return "Standard division or Paravartya"

for divisor in [9, 97, 123, 312, 998, 101, 45]:
    print(f"divisor {divisor}: → {recommend_method(divisor)}")