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