lib/number/z/div_mod.cc

Go to the documentation of this file.

//
// canola - canon canola 1614p emulator
// Copyright (C) 2012 Peter Miller
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License, version 3, as
// published by the Free Software Foundation.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License along
// with this program. If not, see <http://www.gnu.org/licenses/>.
//

#include <lib/ac/assert.h>

#include <lib/number/z.h>


bool
number_z::div_mod(const number_z &numerator, const number_z &denominator,
    number_z &quotient, number_z &remainder)
{
    assert(numerator.is_valid());
    assert(denominator.is_valid());
    if (denominator.is_zero())
    {
        quotient.clear();
        remainder = numerator;
        return false;
    }
    if (denominator.is_one())
    {
        quotient = numerator;
        remainder.clear();
        return true;
    }
    if (numerator.is_zero())
    {
        quotient.clear();
        remainder.clear();
        return true;
    }

    quotient.clear();
    remainder = numerator;
    number_z over(1u);
    number_z under(denominator);
    while (under < remainder)
    {
        under = under.shift_left(1);
        over = over.shift_left(1);
    }
    for (;;)
    {
        over = over.shift_right(1);
        if (over.is_zero())
            break;
        under = under.shift_right(1);
        while (under <= remainder)
        {
            remainder -= under;
            quotient += over;
        }
    }
    return true;
}


// vim: set ts=8 sw=4 et :