Comments for Second Generation Programmer

Comment on Turning Egyptian Division Into Logarithms by secondgenerationprogrammer

secondgenerationprogrammer — Mon, 27 Dec 2021 23:32:09 +0000

In reply to es.

My choice to use (a / b) instead of (a * (1 / b)) is related to how integer division works. Take the example where a = 7 and b = 3. In the first case, (7 / 3) = 2, which yields useful information. However, in the second case, (1 / 3) = 0 and (7 * 0) = 0, which is not useful.

LikeLike

Comment on Turning Egyptian Division Into Logarithms by es

es — Tue, 14 Dec 2021 09:34:51 +0000

Interesting! With my limited background in C++, I understand generic programming as a methodology to develop efficient C++ polymorphic programs.
If an specification says that it is not required to have a commutative group, many authors just refer to a group, contrary to the requirement to be commutative or Abelian group, which explicitly requires a commutative operation. On the other side it seems harmless to me a little redundancy emphasizing non-commutativity.
On the other hand I find the choice to use a-b as an operation in its own right instead of just a short hand for a+(-b) deserves more explanation.
The later is the not just natural but correct choice in the abstract mathematics context, but abstract integers are different from their C++ int, long, long long, counterparts. Although I don’t know C++, I suppose that a + b gives a “wrong” result in C++ when a + b > MAXINT in the abstract maths.
The internal representation of negative numbers may depend on hardware architecture. Your choice to use a – b and a / b as operations not just short notation for a + (-b) and a * (1/b) respectively, may have a justification, but has to be made more clear for those of us which are not aware of such potential source of programming mistakes.
Which are the rules to obey, maybe not those of a group, but other structure [maybe modular], to know which types can be used in the C++ [polymorphic] implementation of the program. That should be part of the specification.
Finally a suggestion. It would be more clear for those like me, who are not aware of the intricate C++ syntax, if you could use first a simpler pseudocode notation, to explain the details, followed to the translation to C++. I find your article very interesting, I also get lost with the C++ in EoP, and fm2gp, the intermediate pseudocode could make all this subject more clear for readers who are not C++ programmers.

LikeLike

Comment on Turning Egyptian Division Into Logarithms by Fernando Pelliccioni

Fernando Pelliccioni — Thu, 18 Jul 2019 11:51:39 +0000

Very nice article!

LikeLike

Comment on Turning Egyptian Division Into Logarithms by secondgenerationprogrammer

secondgenerationprogrammer — Mon, 15 Aug 2016 17:29:36 +0000

In reply to secondgenerationprogrammer.

Having received essentially the same comment from two people I respect (Robert Ramey and Paul McJones), I updated the post to change “noncommutative additive semigroup” to just “semigroup”. Robert, I’m looking forward to your CPPCon session. I won’t be in attendance, but I typically watch the videos after the fact.

LikeLike

Comment on Turning Egyptian Division Into Logarithms by secondgenerationprogrammer

secondgenerationprogrammer — Sun, 14 Aug 2016 23:30:57 +0000

In reply to Evgeny Panasyuk.

Thank you. I sent the link to Alex, Dan, and Paul. An email exchange with Dan and Alex several months ago inspired me to write this post. I’ll check my copy of Knuth tomorrow when I get to work.

LikeLike

Comment on Turning Egyptian Division Into Logarithms by Evgeny Panasyuk

Evgeny Panasyuk — Sun, 14 Aug 2016 17:44:26 +0000

In reply to secondgenerationprogrammer.

Very interesting! I wonder if Alexander Stepanov know about this – I think you should write a letter to him.
I checked Knuth TAOCP – V.1, 1.2.2, Ex.25 – there is note about similarity of division and logarithm algorithms:
“This method [logarithm approximation] is very similar to the method used for division in computer hardware”

LikeLike

Comment on Turning Egyptian Division Into Logarithms by Robert Ramey

Robert Ramey — Sat, 13 Aug 2016 22:08:41 +0000

In reply to secondgenerationprogrammer.

I didn’t know the quote from the book. And I don’t think it’s a great idea for him to redefine accepted mathematical terms in cases such as this. BTW it turns out that the terms semigroup, etc are defined differently by different authors and the “accepted” definition seems to evolve over time. All this adds to the confusion for “the rest of us”

At the risk of hijacking the thread. I’d like to take the opportunity to plug my session “C++, Abstract Algebra, and Applications at CPPCon 2016 this September. I’m hoping that those of us interested in this stuff (i.e. both of us) will find my take on this interesting.

LikeLike

Comment on Turning Egyptian Division Into Logarithms by secondgenerationprogrammer

secondgenerationprogrammer — Sat, 13 Aug 2016 14:10:41 +0000

In reply to Robert Ramey.

Thanks for reading and commenting. Your assertions are correct that the algorithms don’t require commutativity and that polynomials and reals are commutative. The confusion is one of terminology. Here’s a relevant passage from chapter 7 of “From Mathematics to Generic Programming” by Stepanov and Rose: “Since we don’t need commutativity for our algorithm, we’ll say that A is a noncommutative additive semigroup. This means that commutativity is not required; it does not mean that commutativity is not allowed. In other words, every (commutative) additive semigroup is also a noncommutative additive semigroup.” You could easily convince me that “noncommutative additive semigroup” is a poor name for such an entity, but I wanted to be consistent with their terminology.

LikeLike

Comment on Turning Egyptian Division Into Logarithms by Robert Ramey

Robert Ramey — Fri, 12 Aug 2016 19:19:43 +0000

nice article. One minor nit though:

“The algorithm will work with any type that has an associative binary operation (a.k.a. a noncommutative additive semigroup). Examples of noncommutative additive semigroups include real numbers and polynomials.”

I don’t think commutativity is relevant here. It will work with commutative groups as well. An real numbers and polynomials ARE commutative.

LikeLike