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<typena me 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<typena me T>
void divide(T x, T y, T& q, T& r)
{
if (y == 0) {
throw std::domain_err or("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<typena me T>
T divide_quotient (const T& x, const T& y) {
T q;
T r;
divide(x, y, q, r);
return q;
}
template<typena me T>
T divide_remainde r(const T& x, const T& y) {
T q;
T r;
divide(x, y, q, r);
return r;
}
}
namespace binary_arithmet ic_test
{
using namespace cdiggins;
void test(bool b) {
if (!b) {
throw std::runtime_er ror("test failed");
}
}
void test_divide() {
for (int i=0; i < 255; i++) {
for (int j=1; j < 255; j++) {
test(divide_quo tient(i, j) == i / j);
test(divide_rem ainder(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
