Re: algorithms + data structures = programs

arnuld said:


Richard Heathfield wrote:
arnuld said:

<snip>

r := 10*r + d[i]
d[i] := r div 2
r := r-2*d[i]

more *shocking* is its implmentation in PASCAL.

Okay, let's take a look:

program power(output);
{ decimal representation of negative powers of 2 }
const n = 10;
type digit = 0..9;
var i,k,r: integer;
d: array[1..n] of digit;
begin
for k := 1 to n do
begin
write('.');
r := 0;
for i := 1 to k - 1 do
begin
r := 10 * r + d[i];
d[i] := r div 2;
r := r - 2 * d[i];
write(chr(d[i] + ord('0')))
end ;
d[k] := 5;
writeln('5');
end
end .

Yes, okay, I agree. I'm appalled. :-)


hey Rich, i need help.

Um, okay, let's see what we can do with this mess.

We start off with the usual Pascal furniture, and then get on to the meat of
the program:

for k := 1 to n do

So clearly Wirth is only interested in the first ten results.

begin
write('.');

He eschews a leading 0, and gets right into the decimal point.

r := 0;
for i := 1 to k - 1 do

Wirth ex machina - he presumes that each value will take one more decimal
place to represent than the previous value.

First time in, k is 1, so the inner loop doesn't execute. d[1] gets the
value 5, and '.5' is written.

Second time in, k is 2, so i ranges from 1 to 1 (i.e. one iteration
happens).

begin
r := 10 * r + d[i];

i is 1, and d[1] is 5, and r is 0, so r becomes 10 * 0 + 5, which is 5.

d[i] := r div 2;

d[1] becomes half of whatever it is at the moment, so it goes from 5 to 2
(because div is an integer division, so fractions are ignored).

r := r - 2 * d[i];

r becomes its current value less twice d[1]. It was 5, but now it takes the
new value 5 - (2 * 2), which is 1. In other words, it becomes the
*remainder* of the division of d[i] by 2. It would have been better named
'remainder' rather than r. And d[i] is the digit that will be displayed at
position i.

write(chr(d[i] + ord('0')))

This is the equivalent of C's putchar(d[i] + '0') - in other words, it
writes the character equivalent of a particular digit.

end ;
d[k] := 5;

Wirth ex machina again - he presumes the last digit of the representation
will be 5. (He's right, of course, but it would have been nice for the
program to work this out for itself.)

writeln('5');
end

The program does make sense, kind of. It's just written with a whole bunch
of unstated assumptions and is very poorly explained. His explanation
precedes the program:

"Assume that a fraction f is represented by the array d such that

f = sum(i ranges from 1 to k - 1 inclusive) of d[i] * pow(10, -i)

i.e. by its decimal form with k - 1 digits. Now f is to be divided by 2.
This is done by repeating the familiar division operation for all k - 1
digits d[i], starting with i = 1. It consists of dividing the digit by 2,
taking into account a possible carry from the previous position, and of
retaining a remainder r for the previous step."

This could have been expressed somewhat more clearly! And indeed it could
have been avoided completely. I would not have chosen this particular
problem as an illustration of array handling.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
.

Relevant Pages

  • Re: How to convert a number to hex number?
    ... Originally two's compliment representations were used to efficiently ... the same could be said for any ascii representation of numbers. ... The idea of base-complement is that the first digit is the zero digit for ... Also I wanted to see how much slower using strings instead of ints would be. ...
    (comp.lang.python)
  • Re: This calculation is just wrong / computer cant count!
    ... continuing refusal to accept reality is the problem. ... about accuracy and reliability, are simply asinine. ... The final digit is NOT random, ... representation is the 64-bit binary representation; anything else you see is irrelevant. ...
    (microsoft.public.vc.mfc)
  • Re: Well Ordering the Reals
    ... > Okay, I don;t think I understood what you were saying. ... > naturals, you might as well call it something, I suppose. ... In TO's system of "whole numbers", there is a most significant digit and ... > infinite unending string of bits, even if most are generally ignored. ...
    (sci.math)
  • Re: Numeric literals in other than base 10 - was Annoying octal notation
    ... Systems are not defined for radix 1. ... and every number has an infinitely long representation. ... take a 1 digit instead then it becomes workable. ... or the only number that can be represented is infinity. ...
    (comp.lang.python)
  • Re: Comparing two notions of computable number
    ... > to a's nth digit to the right of the decimal point. ... This is a consequence of the fact that in decimal representation small ... for infinite decimal fractions there is not even unique ... latter also with non-unique representation). ...
    (comp.theory)