Diggins PDP #1 : Binary Arithmetic Algorithms (division / multiplication / full_adder )

Discussion in 'C++' started by christopher diggins, May 21, 2005.

  1. Welcome to the first installment of the Diggins Public Domain Posts (PDP).

    There is a significant dearth of good public domain C++ code. All of it
    seems to come with one kind of a license or another, and even though I
    understand the motivations, I believe code is like mathematics and no one
    can really own it. Rather than stand on a pulpit, or debate the
    philosophical merits of the various licenses, I have decided instead to post
    as much code into the public domain as I possibly can in a series of posts
    to comp.lang.c++ called the Diggins Public Domain Posts. I hope you find it
    useful, educational or at the very least entertaining. I welcome any
    comments or suggestions but I am especially keen to see posted improvements
    to the code I share. Enjoy!

    ==

    Diggins PDP #1
    Binary Arithmetic Algorithms

    The following are basic algorithms for binary addition, multiplication and
    division. The algorithms were chosen for simplicity instead of efficiency.
    This code is useful for implementing new kinds of integers and are forming
    the basis of my upcoming fixed_int and big_int classes.

    // public domain by Christopher Diggins

    #include <stdexcept>

    namespace cdiggins
    {
    bool full_adder(bool b1, bool b2, bool& carry)
    {
    bool sum = (b1 ^ b2) ^ carry;
    carry = (b1 && b2) || (b1 && carry) || (b2 && carry);
    return sum;
    }

    template<typename T>
    T multiply(T x, T y)
    {
    T ret = 0;
    while (y > 0)
    {
    if (y & 1) {
    ret += x;
    }
    y >>= 1;
    x <<= 1;
    }
    return ret;
    }

    template<typename T>
    void divide(T x, T y, T& q, T& r)
    {
    if (y == 0) {
    throw std::domain_error("division by zero undefined");
    }
    if (x == 0) {
    q = 0;
    r = 0;
    return;
    }
    if (x <= y) {
    if (x == y) {
    q = 1;
    r = 0;
    return;
    }
    else {
    q = 0;
    r = x;
    return;
    }
    }
    q = 0;
    r = x;
    int n=1;
    while (y < x) {
    y <<= 1;
    n++;
    }
    while (n--) {
    q <<= 1;
    if (y <= r) {
    q |= 1;
    r = r - y;
    }
    y >>= 1;
    }
    }

    template<typename T>
    T divide_quotient(const T& x, const T& y) {
    T q;
    T r;
    divide(x, y, q, r);
    return q;
    }

    template<typename T>
    T divide_remainder(const T& x, const T& y) {
    T q;
    T r;
    divide(x, y, q, r);
    return r;
    }
    }

    namespace binary_arithmetic_test
    {
    using namespace cdiggins;

    void test(bool b) {
    if (!b) {
    throw std::runtime_error("test failed");
    }
    }

    void test_divide() {
    for (int i=0; i < 255; i++) {
    for (int j=1; j < 255; j++) {
    test(divide_quotient(i, j) == i / j);
    test(divide_remainder(i, j) == i % j);
    }
    }
    }

    void test_multiply() {
    for (int i=0; i < 255; i++) {
    for (int j=0; j < 255; j++) {
    test(multiply(i, j) == i * j);
    }
    }
    }

    void test_full_adder() {
    bool carry = true;
    test(full_adder(true, true, carry) == true);
    test(carry == true);
    test(full_adder(true, false, carry) == false);
    test(carry == true);
    test(full_adder(false, true, carry) == false);
    test(carry == true);
    test(full_adder(false, false, carry) == true);
    test(carry == false);
    test(full_adder(true, false, carry) == true);
    test(carry == false);
    test(full_adder(false, true, carry) == true);
    test(carry == false);
    test(full_adder(true, true, carry) == false);
    test(carry == true);
    }

    void test_main()
    {
    test_divide();
    test_multiply();
    test_full_adder();
    }
    }

    --
    Christopher Diggins
    http://www.cdiggins.com
    christopher diggins, May 21, 2005
    #1
    1. Advertising

  2. christopher diggins

    Guest

    christopher diggins wrote:
    > Welcome to the first installment of the Diggins Public Domain Posts

    (PDP).
    >
    > There is a significant dearth of good public domain C++ code. All of

    it
    > seems to come with one kind of a license or another, and even though

    I
    > understand the motivations, I believe code is like mathematics and no

    one
    > can really own it.


    Literature is like letters too, but it has a perceived worth that's
    worth honoring if you combine those letters in entertaining or
    informative ways...

    > Rather than stand on a pulpit, or debate the
    > philosophical merits of the various licenses, I have decided instead

    to post
    > as much code into the public domain as I possibly can in a series of

    posts
    > to comp.lang.c++ called the Diggins Public Domain Posts. I hope you

    find it
    > useful, educational or at the very least entertaining. I welcome any
    > comments or suggestions but I am especially keen to see posted

    improvements
    > to the code I share. Enjoy!


    I admire your idealism, but...

    I found several obvious bugs in a one-minute sweep through the code.
    Mostly they're the kind of bugs novices introduce. Several result in
    infinite loops for seemingly innocuous inputs. And those are the kind
    of bugs that eat up *lots* of your time; hence they cost you way more
    money than you save by getting something for free.

    Useful, educational, and/or entertaining? Only as a cautionary tale.

    P.J. Plauger
    Dinkumware, Ltd.
    http://www.dinkumware.com
    , May 22, 2005
    #2
    1. Advertising

  3. <> wrote in message
    news:...
    > christopher diggins wrote:
    >
    > Literature is like letters too, but it has a perceived worth that's
    > worth honoring if you combine those letters in entertaining or
    > informative ways...


    This is a valid point though I don't agree fully with the analogy. I should
    probably steer clear from the debate, because my views are bound to be
    unpopular and controversial. I just would like to encourage contributions to
    the public domain.

    > I admire your idealism, but...
    >
    > I found several obvious bugs in a one-minute sweep through the code.
    > Mostly they're the kind of bugs novices introduce. Several result in
    > infinite loops for seemingly innocuous inputs.


    If you would share any of the bugs with me (or at the very least some
    examples of broken input), I would be most appreciative. One big mistake I
    made is that I should have made explicit that the multiplication / division
    algorithms were only intended for positive integer values.

    > And those are the kind
    > of bugs that eat up *lots* of your time; hence they cost you way more
    > money than you save by getting something for free.


    Sure, but hopefully people will point these bugs out, and then this free
    code can be improved, and then perhaps become truly useful.

    > Useful, educational, and/or entertaining? Only as a cautionary tale.


    A cautionary tale against what?

    Thank you for responding to the post. I am very glad it at least provoked
    some kind of reaction.

    --
    Christopher Diggins
    christopher diggins, May 22, 2005
    #3
  4. Diggins PDP #1.1 : Binary Arithmetic Algorithms

    // The Diggins PDP (Public Domain Post) #1.1
    // Public Domain code by Christopher Diggins, May 22, 2005
    // corrected division bugs posted for version 1.0 on May 21
    // thanks to P.J. Plauger for pointing out errors
    //
    // Description:
    // - simple multiplication algorithm of arbitrary unsigned integers using
    shifts and addition
    // - simple division algorithm of arbitrary unsigned integers using shifts
    and subtraction
    // - significant digit counting function
    // - full adder logic gate emulation function

    #ifndef BINARY_ARITHMETIC_HPP
    #define BINARY_ARITHMETIC_HPP

    #include <stdexcept>
    #include <cassert>

    namespace cdiggins
    {
    bool full_adder(bool b1, bool b2, bool& carry)
    {
    bool sum = (b1 ^ b2) ^ carry;
    carry = (b1 && b2) || (b1 && carry) || (b2 && carry);
    return sum;
    }

    template<typename T>
    unsigned int count_significant_digits(T x) {
    unsigned int n = 0;
    while (x > 0) {
    ++n;
    x >>= 1;
    }
    return n;
    }

    template<typename T>
    T multiply(T x, T y)
    {
    // this multiply accepts only non-negative integer values
    assert(x >= 0);
    assert(y >= 0);
    T ret = 0;
    while (y > 0)
    {
    if (y & 1) {
    ret += x;
    }
    y >>= 1;
    x <<= 1;
    }
    return ret;
    }

    template<typename T>
    void divide(T x, T y, T& q, T& r)
    {
    // this divide accepts only non-negative integer values
    assert(x >= 0);
    assert(y >= 0);
    if (y == 0) {
    throw std::domain_error("division by zero undefined");
    }
    if (x == 0) {
    q = 0;
    r = 0;
    return;
    }
    if (y == x) {
    q = 1;
    r = 0;
    return;
    }

    q = 0;
    r = x;

    if (y > x) {
    return;
    }

    // count significant digits in divisor and dividend
    unsigned int sig_x = count_significant_digits(x);
    unsigned int sig_y = count_significant_digits(y);

    // check against my own stupidity
    assert(sig_x >= sig_y);

    // align the divisor with the dividend
    unsigned int n = (sig_x - sig_y);
    y <<= n;

    n += 1; // make sure the loop executes the right number of times

    // long division algorithm, shift and subtract
    while (n--)
    {
    q <<= 1; // shift the quotient to the left
    if (y <= r)
    {
    q |= 1; // add a new digit to quotient
    r = r - y; // subtract from the remained
    }
    y >>= 1; // shift the divisor to the right
    }
    }

    template<typename T>
    T divide_quotient(const T& x, const T& y) {
    T q;
    T r;
    divide(x, y, q, r);
    return q;
    }

    template<typename T>
    T divide_remainder(const T& x, const T& y) {
    T q;
    T r;
    divide(x, y, q, r);
    return r;
    }
    }

    namespace binary_arithmetic_test
    {
    using namespace cdiggins;

    void test(bool b) {
    if (!b) {
    throw std::runtime_error("test failed");
    }
    }

    void test_divide() {
    for (unsigned char i=0; i < 0xFF; i++) {
    for (unsigned char j=1; j < 0xFF; j++) {
    test(divide_quotient(i, j) == i / j);
    test(divide_remainder(i, j) == i % j);
    }
    }
    }

    void test_multiply() {
    for (int i=0; i < 0xFF; i++) {
    for (int j=0; j < 0xFF; j++) {
    test(multiply(i, j) == i * j);
    }
    }
    }

    void test_full_adder() {
    bool carry = true;
    test(full_adder(true, true, carry) == true);
    test(carry == true);
    test(full_adder(true, false, carry) == false);
    test(carry == true);
    test(full_adder(false, true, carry) == false);
    test(carry == true);
    test(full_adder(false, false, carry) == true);
    test(carry == false);
    test(full_adder(true, false, carry) == true);
    test(carry == false);
    test(full_adder(false, true, carry) == true);
    test(carry == false);
    test(full_adder(true, true, carry) == false);
    test(carry == true);
    }

    void test_main()
    {
    test_divide();
    test_multiply();
    test_full_adder();
    }
    }

    #endif
    christopher diggins, May 22, 2005
    #4
  5. > I found several obvious bugs in a one-minute sweep through the code.
    > Mostly they're the kind of bugs novices introduce. Several result in
    > infinite loops for seemingly innocuous inputs. And those are the kind
    > of bugs that eat up *lots* of your time; hence they cost you way more
    > money than you save by getting something for free.


    I think I found the bugs you referred to. I have posted a new version.
    Thanks for pointing out that I had errors, I really appreciate it, and I
    credit you in the new version I posted.

    I think however you were trying to make the point that free code can be
    expensive because quality can be so hard to assure. I fully agree, and I
    think this is why there will always be a market for commercial code.

    I should point out that my qualms aren't with commercial code, but rather
    with the various "free" licenses. The idea of restricting something and
    calling it free is offensive to me. My goal is to combat this by simply
    trying to contribute to the public domain code base as much as I can, and
    perhaps encourage others to contribute as well.

    Maybe I misread your tone, but I would have thought that commercial library
    authours such as yourself would be more receptive and supportive of the idea
    of public domain code over free but licensed code, because there is
    absolutely no restriction over the usage in commercial libraries.

    Christopher Diggins
    christopher diggins, May 22, 2005
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. christopher diggins
    Replies:
    1
    Views:
    380
    Rapscallion
    May 23, 2005
  2. christopher diggins
    Replies:
    0
    Views:
    438
    christopher diggins
    May 24, 2005
  3. christopher diggins

    Diggins PDP #3 : arbitrary precision integers

    christopher diggins, May 24, 2005, in forum: C++
    Replies:
    0
    Views:
    362
    christopher diggins
    May 24, 2005
  4. christopher diggins

    Diggins PDP #4 : FFT (Fast Fourier Transform)

    christopher diggins, Jun 2, 2005, in forum: C++
    Replies:
    0
    Views:
    498
    christopher diggins
    Jun 2, 2005
  5. christopher diggins
    Replies:
    1
    Views:
    339
    christopher diggins
    Jun 3, 2005
Loading...

Share This Page