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

[christopher diggins]

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();
}
}

 

[pjp]

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

 

[christopher diggins]

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]

// 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]

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