Division of two positive long numbers. Sample implementation in Lua.

long_div.lua

--[[
  Long number represented as Lua table. Lowest digits at lowest indexes.
  1-base. "len" field for length. No sign. Zero has "len" = 0.

  271828 =
    {[1] = 2, [2] = 7, [3] = 1, [4] = 8, [5] = 2, [6] = 8; len = 6}

]]

local BASE = 10
print('BASE', BASE)

local long_to_str =
  -- Return string with long number:
  function(A)
    local result = {}
    if (A.len == 0) then
      result = {'0'}
    else
      for i = A.len, 1, -1 do
        result[#result + 1] = tostring(A[i]) or '0'
      end
    end
    result = table.concat(result, '_')
    return result
  end

local long_clone =
  -- Returns copy of long number:
  function(A)
    local result = {}
    for i = 1, A.len do
      result[i] = A[i]
    end
    result.len = A.len
    return result
  end

local long_greater_or_equal =
  -- Return true if first long natural number >= than second:
  function(A, B)
    local result
    if (A.len > B.len) then
      result = true
    elseif (A.len < B.len) then
      result = false
    else
      result = false
      for i = A.len, 1, -1 do
        if (A[i] > B[i]) then
          result = true
          break
        elseif (A[i] < B[i]) then
          break
        end
      end
    end
    return result
  end

local long_mul_by_dig =
  -- Multiply long number by digit starting from least signifacant digits:
  function(A, digit)
    local result = {len = 0}
    local carry = 0
    while ((result.len < A.len) or (carry ~= 0)) do
      result.len = result.len + 1
      carry = carry + (A[result.len] or 0) * digit
      result[result.len] = carry % BASE
      carry = carry // BASE
    end
    return result
  end

local long_subtract =
  -- Subtract long natural numbers, starting from least significant digits.
  function(A, B)
    if not long_greater_or_equal(A, B) then
      return long_clone(A)
    end
    -- Now we know that A.len >= B.len.

    local result = {len = 0}

    local borrow = 0
    while ((result.len < A.len) or (borrow ~= 0)) do
      result.len = result.len + 1
      borrow = A[result.len] - (B[result.len] or 0) - borrow + BASE
      result[result.len] = borrow % BASE
      if (borrow < BASE) then
        borrow = 1
      else
        borrow = 0
      end
    end

    -- Remove possible leading zeroes:
    while (result[result.len] == 0) do
      result[result.len] = nil
      result.len = result.len - 1
    end

    --[[
    print(
      ('%s - %s = %s'):
      format(long_to_str(A), long_to_str(B), long_to_str(result))
    )
    ]]

    return result
  end

local long_shift_left =
  -- Shift long number by left by given value.
  function(A, n)
    local result = long_clone(A)
    for i = 1, n do
      result[i] = 0
    end
    for i = 1, A.len do
      result[i + n] = A[i]
    end
    result.len = result.len + n

    --[[
    print(
      ('%s << %d = %s'):
      format(
        long_to_str(A),
        n,
        long_to_str(result)
      )
    )
    ]]

    return result
  end

local get_quotient_digit_naive =
  --[[
    Calculate greatest quotient digit for two long numbers.

    Numbers should be near same length.

    Requires near (BASE / 2) long subtractions per call. Simple.
  ]]
  function(A, B)
    local result = 0
    local A_clone = long_clone(A)
    while long_greater_or_equal(A_clone, B) do
      A_clone = long_subtract(A_clone, B)
      result = result + 1
    end
    return result
  end

local get_quotient_digit_advanced =
  --[[
    Requires 1 to 2 long subtractions per call, one multiplication
    long by digit, one division long by digit. Complex.

    See D.E.C. AoCP, 4.3.1, Algorithm D.
    (Explained badly, best style of 70-ies.)
  ]]
  function(A, B)
    assert(true)
  end

-- Chose implementation:
local get_quotient_digit = get_quotient_digit_naive

local long_div_mod =
  --[[
    For two long natural numbers, numerator and denominator,
    return two long numbers, quotient and remainder.

    Quotient digits is filled from greatest to lowest.
  ]]
  function(A, B)
    local quotient, remainder = {len = 0}, {len = 0}
    if not long_greater_or_equal(A, B) then
      -- if (A < B) then Q = 0, R = A
      remainder = long_clone(A)
      return quotient, remainder
    end

    local numerator, denominator = long_clone(A), long_clone(B)

    local denom_shift = numerator.len - denominator.len
    while long_greater_or_equal(numerator, denominator) do
      local denom_shifted = long_shift_left(denominator, denom_shift)
      local q_dig = get_quotient_digit(numerator, denom_shifted)
      quotient.len = quotient.len + 1
      quotient[quotient.len] = q_dig
      numerator = long_subtract(numerator, long_mul_by_dig(denom_shifted, q_dig))
      denom_shift = denom_shift - 1
    end
    remainder = numerator

    local quotient_reverse = {len = quotient.len}
    for i = 1, quotient.len do
      quotient_reverse[i] = quotient[quotient.len - i + 1]
    end
    quotient = quotient_reverse

    print(
      ('long_div_mod(%s, %s) = %s, %s'):
      format(
        long_to_str(A),
        long_to_str(B),
        long_to_str(quotient),
        long_to_str(remainder)
      )
    )

    return quotient, remainder
  end

local A = {3, 9, 7, 8; len = 4}
-- A = 8793, A[1] = 3, ..., A[A.len] = 8

local B = {7, 7, 2; len = 3}
-- B = 277

local Q, R = long_div_mod(A, B)