The Joy Of Programming

2007-02-22T02:56:00.000-08:00

The Joy Of Programming

In Feb issue of Linux for You (http://www.linuxforu.com/index.php) magazine Joy Of Programming column, I
mentioned a floating point problem:
"Since the floating point arithmetic is not accurate, the operations can result in loss of precision and rounding errors.
In the loop, when the value of f reaches 16777216.0, adding one doesn’t increment the value of f by one, but gets
rounded off.

You can verify it with the following code segment:

float f = 16777216.0;
assert(f == (f + 1));

This doesn’t fail with an assertion failure and works fine!

"An astute reader observed that, if we change f + 1 to f + 1.0, it does fail!
The reason is that 1.0 is a double value. f + 1.0 becomes a double expression, which results in the
value 16777217.0, and hence the assertion fails.

Note that the code here assumes that the compiler is in C89 mode. In K&R mode, all floating
point operations are done in double, so the assertion will fail!

2007-02-22T02:53:00.000-08:00

What can simple software problems do? It can cause even a rocket mission to get aborted, as happened with Ariane5 accident:

http://sunnyday.mit.edu/accidents/Ariane5accidentreport.html

"The internal SRI software exception was caused during execution of a data conversion from 64-bit floating point to 16-bit signed integer value. The floating point number which was converted had a value greater than what could be represented by a 16-bit signed integer. This resulted in an Operand Error. The data conversion instructions (in Ada code) were not protected from causing an Operand Error, although other conversions of comparable variables in the same place in the code were protected.

The error occurred in a part of the software that only performs alignment of the strap-down inertial platform. This software module computes meaningful results only before lift-off. As soon as the launcher lifts off, this function serves no purpose."

The Conceptual Simplicity of Pascal

2006-03-03T03:56:00.000-08:00

Conceptual simplicity is something very important in the modern, complex, maddening world .
I thought about this when I just got a chance to take a look at the pascal sources:

http://invent.ucsd.edu/technology/cases/1995-prior/SD1991-807.htm

Its so compact and clear considering to the contributions and advancements it made in
programming languages/compilers!

Decimal Arithmetic

2006-01-19T23:25:00.000-08:00

Lack of support for decimal arithmetic is a painpoint for commercial software implementations.Put simply, the existing ieee 754 standard for floating points isn't much suitable for representing realworld decimal values (in other words, using binary floats with base 2 is not preferable, a float representation with base 10 is better).

Languages currently have not-so-good alternatives. C# supports the decimal type as a primitive type (borrowed from SQL). This type occupies 128 bytes and provides higher precision. It can be valuable in monetary calculations where it is necessary to represent exact values. For similar functionality, C++ provides the long double type (but don’t be mislead- implementations provide its supportthro following IEEE extended precision fp standard). Java provides the java.math.BigDecimal class- that’s much better; but since no H/W support is there, and all values calculated, the application will perform terribly slow if BigDecimal is used extensively. There are a few proposalswith IEEE for decimal arithmetic, and if its approved, things will be much better.

new meaning of static in C99

2006-01-13T07:24:00.000-08:00

C99 provides a new meaning for static, consider:

void bar (int b[static 100]);

This is to ensure that bar will take an array argument which is promised to have size 100 or more. This is an optimization hint for the compiler (those that do vectorization).

Standard C++ TR1

2005-12-07T22:30:00.000-08:00

The Standard C++ library has got a new TR1 (Technical Report 1). There are major additions to standard library with this (though TR1 is not part of the standard yet). Major components added include shared_ptr (and its relative weak_ptr), unordered associative containers, c99 compatibility features, tuples etc. Here is a small Q & A on questions you might have on TR1.

Q: A weak_ptr is for avoiding the shared_ptr circular reference. How can we ensure that the resource isn't freed when accessing a resource through a weak_ptr.
A: When we use a weak_ptr to access a resource when use_count might become zero, we can use "lock" function.
weak_ptr::expired() is the function that can be used to check if the memory resource has got freed or not.

Q: How to get a legacy C array out of a tr1::array?
A: Use array::data() function to get the equivalent C-style array from a tr1::array.

Q: Since using tr1::array is recommended over using legacy C style array, will it result in more type_info objects added to the object file and that the object file will become bigger?
A: type_info objects are per-class datastructures, so its unlikely that it will result in any significant change. Moreover, tr1::array is not polymorphic, so a compiler need not put type_info objects in the object file.

Q: What are the compiler changes that will be needed to accommodate TR1?
A: The C99 changes compatibility addition to TR1 for math libraries is one. If there are any other changes needed are not clear yet, but its unlikely that any changes will be needed.

The Power of C++ Library

2005-11-23T00:57:00.000-08:00

Sometimes, I am just amazed by the power of the C++ standard library. Check the following simple
code:

#include
#include
#include
#include
using namespace std;

int main() {
ostringstream out(ios_base::in | ios_base::out);
ostream mycout(cin.rdbuf());
out << mycout.rdbuf();
printf("%s\n", out.str().c_str());
}

It reads the input, copies the output to the temporary ostream object. Then it puts whatever in the ostream to a string stream
and then, uses printf to get the underlying C string and put it in stdout. Another variation of this program is this:

#include
using namespace std;

int main() {
cout << cin.rdbuf();
}

This copies the standard input to stdout. The performance is also very good, comparable to the similar program written
with low-level C routines!

Programming language ratings

2005-10-23T22:27:00.000-07:00

I (like many others) don't believe in rating programming languages, but it is still intructive/interesting to see whats happening in the programming language community. Recently, I saw one such rating in http://www.tiobe.com/tpci.htm.

Interesting to see C rated much higher than C++.

"October Headline: ColdFusion enters Top 20

The TIOBE Programming Community index gives an indication of the popularity of programming languages. The index is updated once a month. The ratings are based on the world-wide availability of skilled engineers, courses and third party vendors. The popular search engines Google, MSN, and Yahoo! are used to calculate the ratings. Observe that the TPC index is not about the best programming language or the language in which most lines of code have been written.

The index can be used to check whether your programming skills are still up to date or to make a strategic decision about what programming language should be adopted when starting to build a new software system...."

Position (Position) Programming Language Ratings (Ratings) Status

1 Java 21.871% +4.82% A
2 C 18.773% +0.60% A
3 C++ 11.820% -3.75% A
.
7 C# 3.462% +1.82% A
.
14 COBOL 0.859% +0.15% A
15 Lisp/Scheme 0.665% +0.23% A-
16 Fortran 0.640% +0.28% B
17 Ada 0.590% +0.23% B
18 Pascal 0.567% +0.10% B
.

Floating Point Fractional Constants in C99

2005-10-19T02:26:00.000-07:00

Today, when looking into the C99 standard for clarifying a doubt I had, I encountered a
strange construct in C99 hexadecimal constants where "P" is allowed to be present. Later,
with exprimentation, I found that it is for supporting floating point "fractional" constants.

For example, 0x1P1 means 1 * 2 power 1 => 2
0x1P-1 means 1 * 2 power -1 => 0.5

Note that this construct is only allowed for hex-constants and the power is 2 not 10 or 16.
With this, just like the e/E notation for exponents, fractional values can be conveniently expressed
with P format. For example to represent a fraction, say, EPSILON, I can use P notation:

#define EPSILON 0X1P-23F

instead of:

#define EPSILON 1.19209e-07

But I don't know what P means (may be "Power of"?).

Thunks in C++

2005-10-13T09:49:00.001-07:00

Thunks in C++

Advanced C++ programmers might know about "thunks". Thunks are compiler generated very small functions that typically do some pointer or address adjutment. Why is it needed? Consider

delete [] arr;

where arr is points to an array of 10 elements from dynamically allocated memory. When you do delete, how does the size of array obtained and correct number of destructors are called? This can be implented by a compiler by providing thunks: a small function that will retrieve the number of elements in a dynamically allocated array from memory and give it to the delete so that it will call the destructors that many number of times. Usually, thunks are used in vtables where a this pointer manipulation for doing a virtual function call for complex cases in multiple virtual inheritance.

This is all fine, but I came across an intersting fact that "thunks" were originally introduced in compiler implementations during Algol days. Algol has two argument passing mechanisms: pass by value and pass by name. Pass by name is problematic, and works just like macros in C. With pass by value, the name is bound at runtime, an a replacement is done. That sounds like magic, how can it be done?
P. Z. Ingerman is believed to have invented thunks in 1961 as a mechanism of implementing pass by name to bind actual parameters to formal definitions. Pass by name didn't live the test of time and later programming languages didn't use it, but the term "thunk" stuck. Interesting indeed!

Thunks in C++

2005-10-13T09:49:00.000-07:00

The Joy of Programming

2005-10-09T22:48:00.000-07:00

Brahmagupta's Riddle

I recently came across ancient Indian mathematician Brahmagupta's quote "A person who can, within a year, solve x^2 - 92y^2 = 1 is a mathematician." (x square - 92 multiplied by y square = 1).

Since I am no mathematician but a programmer, I tried writing a program to find out the values for x and y.

x^2 - 92y^2 = 1
=> x^2 = 1 + 92y^2
=> x = rootof (1 + 92y^2)

So, my program can vary an integer value y and do floating point computation for the formula rootof (1 + 92y^2), and check if the result is an integer.

But later, I thought, its better to keep it as integer and compute it using two for loops to avoid floating point computation:

#include
#include
int main() {
int x, y;
for(x = 1; x <= SHRT_MAX; x++) {
for(y = 1; y <= SHRT_MAX; y++) {
if ( (x * x) == (1 + 92 * y * y)) {
printf("x = %d, y = %d", x, y);
break;
}
}
}
}

And for my surprise, it found the answer in a few seconds: it prints x = 1151, y = 120
1151 * 1151 == 1 + 92 * 120 * 120
=> 1324801 == 1 + 92 * 14400
=> 1324801 == 1 + 1324800
=> 1324801 == 1324801

Well, even now I don't understand the complexity of the original problem. Can somebody who is good in mathematics explain it to me?

I was also wondering how this program can be made more efficient.