Help with "Cyclic Addition" function 
Author Message
 Help with "Cyclic Addition" function

Hello....

     I am working on a program in Turbo Pascal which in one section
requires a
function to do what I call -- for lack of a better term -- "cyclic
addition".
The input and output for the function is a long integer.  Within the
function
each element of the of the number input into the function is added to
each other
to create a new number which in turn is fed into the loop until a number
between
1 and 9 is achieved.

             Example:  1971 =
                       1 + 9 + 7 + 1 =
                       18

                       18 =
                       1 + 8 =
                       9

At this point the output of this function becomes the input for a case
statement
which selects the next function to branch to according to the input it
receives.

     I have created such a function called "ReduceNumber" in this
example but
I am not completely happy with it.  In my opinion, it relies too heavily
on brute
force also I predict that it will fail if passed a very large number.  I
am
hoping that someone here can suggest an alternative approach which will
allow a
string of any length for input and also allow me to write tighter code.

     Thank you all in advance

David Solly

Function ReduceNumber (Number : LongInt) : LongInt;

{
   REDNO2.INC
   Program:  Reduce Number (Function)

   Purpose:  Creates quasi-random numbers for games of fortune and
             chance.

   History:  Written by David Solly
             19 September 1996

   Methodology:

             Add each element to the next within a number.
             Example:  1971 =
                       1 + 9 + 7 + 1 =
                       18

                       18 =
                       1 + 8 =
                       9

Quote:
}

Var
   LN1, Rmd, Acc, Temp, k : LongInt;
   i, E: Integer;

Function Pow(B, E : Double) : Double;

{ Local power function }

Begin
  Pow := Exp(E * Ln(B))
End; { Function Pow }

Begin

   { Initiate the variables }

   LN1 := Number;         { The local copy of the number to reduce }
   Acc := 0;              { Clear Acc.  Prob. redundant but safe   }
   E   := 0;              { Number of decimal places counted       }
   Rmd := 0;              { Clear Rmd.  Prob. redundant but safe   }

   {
      Calculate the number of decimal places by repeatedly dividing
      the number by 10
   }

   Repeat
      LN1 := LN1 div 10;
      Inc(E);             { Count number of decimal places         }
   Until LN1 <= 9;

   {
      Reduce by dividing by diminising powers of 10 and
      adding the result to the variable Acc.
   }

   For i := E downto 0 do
   Begin
      k := Trunc(Pow(10, i)); { k = 10^i

Quote:
}

      Temp := Number div k;   { Divide the number
Quote:
}

      Rmd  := Number mod k;   { Find what remains
Quote:
}

      Acc  := Acc + Temp;     { Cumulative addition of the above results
Quote:
}

      Number  := Rmd;         { Feed Rmd back into the loop
Quote:
}

   End;

   ReduceNumber := Acc;

End;  { Function ReduceNumber }



Thu, 06 Mar 2003 03:00:00 GMT  
 Help with "Cyclic Addition" function
In comp.programming

Quote:

>     I am working on a program in Turbo Pascal which in one section
>requires a
>function to do what I call -- for lack of a better term -- "cyclic
>addition".
>The input and output for the function is a long integer.  Within the
>function
>each element of the of the number input into the function is added to
>each other
>to create a new number which in turn is fed into the loop until a number
>between
>1 and 9 is achieved.

>             Example:  1971 =
>                       1 + 9 + 7 + 1 =
>                       18

>                       18 =
>                       1 + 8 =
>                       9

This is a checksum.  I haven't done Pascal in years, so here is a C
version.  The % is the modulus operator:

long CalcCheckSum(long val)          
{                                    
  long result = 0;                  

  for( ; val; val /= 10)            
    result += val % 10;

  return result % 10;                    

- Show quoted text -

Quote:
}                                    



Fri, 07 Mar 2003 11:42:14 GMT  
 Help with "Cyclic Addition" function

Quote:

>>             Example:  1971 =
>>                       1 + 9 + 7 + 1 =
>>                       18

>>                       18 =
>>                       1 + 8 =
>>                       9
>This is a checksum.  I haven't done Pascal in years, so here is a C
>version.  The % is the modulus operator:
>long CalcCheckSum(long val)          
>{                                    
>  long result = 0;                  

>  for( ; val; val /= 10)            
>    result += val % 10;

>  return result % 10;                    
>}                                    

Actually you misunderstood the problem. What you're doing is, given
d[n]*b^(n) + d[n-1]*b^(n-1) + ... + d[0]*b^(0)

Checksum = (d[n] + d[n-1] ... + d[0]) mod b

That's not what he wants.



Fri, 07 Mar 2003 12:19:11 GMT  
 Help with "Cyclic Addition" function

Quote:

>Hello....

>     I am working on a program in Turbo Pascal which in one section
>requires a
>function to do what I call -- for lack of a better term -- "cyclic
>addition".
>The input and output for the function is a long integer.  Within the
>function
>each element of the of the number input into the function is added to
>each other
>to create a new number which in turn is fed into the loop until a number
>between
>1 and 9 is achieved.

>             Example:  1971 =
>                       1 + 9 + 7 + 1 =
>                       18

>                       18 =
>                       1 + 8 =
>                       9

This is basically a matter of breaking down the problem
in the right way.

Consider 1971 => 18 as a transformation. Let's call it
SumOfDigits.

Example: SumOfDigits(456) => 15

Then we can use this transformation function to go from
1971 to 18, and from 18 to 9. But when do you stop? When
you reach a number that's smaller than 10, right? That's
a termination condition, let's call this Stop.

Example: Stop(7) => true, Stop(45) => false

Now that we have a transformation function and a termination
condition. We need an iterative process to apply the
transformation function repeatedly to the original number
until we reach the termination condition. There are two
general approaches to denote this iterative process: recursion,
and loop.

loop:

get input
while (termination-condition is not true)
   input := transform(input)

recursion:

function iterate(input)
  if (termination-condition)
    then input;
    else iterate(transform(input));

Hope this helps.

Dan.



Fri, 07 Mar 2003 12:43:06 GMT  
 Help with "Cyclic Addition" function
In comp.programming

Quote:

>Actually you misunderstood the problem. What you're doing is, given
>d[n]*b^(n) + d[n-1]*b^(n-1) + ... + d[0]*b^(0)

>Checksum = (d[n] + d[n-1] ... + d[0]) mod b

>That's not what he wants.

Oops!  You are right.  I even tested it <blush> but I imput 1981 instead of
1971 :)


Fri, 07 Mar 2003 13:12:02 GMT  
 Help with "Cyclic Addition" function
In comp.programming

Quote:

>Oops!  You are right.  I even tested it <blush> but I imput 1981 instead of
>1971 :)

Here you go, quick modification for a recursive solution.  Hope I don't
embarrass myself on this one :)

long SumDigitsToSingle(long val)
{
  long result = 0;

  for( ; val; val /= 10)
    result += val % 10;

  // Keep calling ourself till we're single digit
  if( result > 10)
          return SumDigitsToSingle(result);
  else
          return result;

Quote:
}

Bruce


Fri, 07 Mar 2003 13:25:42 GMT  
 Help with "Cyclic Addition" function

Quote:

>Here you go, quick modification for a recursive solution.  Hope I don't
>embarrass myself on this one :)

>long SumDigitsToSingle(long val)
>{
>  long result = 0;

>  for( ; val; val /= 10)
>    result += val % 10;

>  // Keep calling ourself till we're single digit
>  if( result > 10)
>      return SumDigitsToSingle(result);
>  else
>      return result;
>}

Actually, (result > 10) should be (result >= 10)

In C, as long as tail-call optimization isn't guaranteed,
I'd just have

long SumDigitsToSingle(long val)
{
    long tempResult;
    while (val > 9)
    {
        tempResult = 0;
        for (; val; val /= 10)
            tempResult += val % 10;
        val = tempResult;

    }
    return val;

Quote:
}

Dan.


Fri, 07 Mar 2003 13:34:28 GMT  
 Help with "Cyclic Addition" function

Quote:


> >long SumDigitsToSingle(long val)
> >{
> >  long result = 0;

> >  for( ; val; val /= 10)
> >    result += val % 10;

> >  // Keep calling ourself till we're single digit
> >  if( result > 10)
> >         return SumDigitsToSingle(result);
> >  else
> >         return result;
> >}
> Actually, (result > 10) should be (result >= 10)

> In C, as long as tail-call optimization isn't guaranteed,
> I'd just have

> long SumDigitsToSingle(long val)
> {
>     long tempResult;
>     while (val > 9)
>     {
>         tempResult = 0;
>         for (; val; val /= 10)
>             tempResult += val % 10;
>         val = tempResult;

>     }
>     return val;
> }

I've been reading this thread for a while, but hasn't anybody noticed
the following relation?

        sum(num) = sum(num/10+num%10)

Given this simple observation, the following code snippet doesn't come
as a surprise:

        int sum(int n) {

                while (n >= 10)
                        n= n/10+n%10;

                return n;
        }

kind regards,




Fri, 07 Mar 2003 03:00:00 GMT  
 Help with "Cyclic Addition" function

Quote:

>Hello....

>     I am working on a program in Turbo Pascal which in one section
>requires a
>function to do what I call -- for lack of a better term -- "cyclic
>addition".
>The input and output for the function is a long integer.  Within the
>function
>each element of the of the number input into the function is added to
>each other
>to create a new number which in turn is fed into the loop until a number
>between
>1 and 9 is achieved.

>             Example:  1971 =
>                       1 + 9 + 7 + 1 =
>                       18

>                       18 =
>                       1 + 8 =
>                       9

>At this point the output of this function becomes the input for a case
>statement
>which selects the next function to branch to according to the input it
>receives.

This procedure is known as "casting out nines" and was widely taught
and used as a technique for verifying calculations back in the dreary
old days of the last millennium when people did arithmetic by hand.

There have been many interesting and informative suggestions as to
various ways in which your task might be performed.  May I suggest,
however, that it might be simpler and more efficient to simply
do:
        answer = input % 9

since you evidently do have the modulo function available.


http://www.*-*-*.com/
"It was half way to Rivendell when the {*filter*} began to take hold"
Hunter S Tolkien "Fear and Loathing in Barad Dur" - Iain Bowen



Fri, 07 Mar 2003 03:00:00 GMT  
 Help with "Cyclic Addition" function

Quote:
>I've been reading this thread for a while, but hasn't anybody noticed
>the following relation?

>    sum(num) = sum(num/10+num%10)

>Given this simple observation, the following code snippet doesn't come
>as a surprise:

>    int sum(int n) {

>            while (n >= 10)
>                    n= n/10+n%10;

>            return n;
>    }

Yup. You're going way too fast though.

More generally,

sum(a + b) = sum(sum(a) + sum(b)) ... [1]
sum(10 * a) = sum(a)

From there, you get

sum(n) where n = a*10 + b

sum(n) = sum(a*10 + b)
       = sum(sum(a*10) + sum(b))
       = sum(sum(a) + sum(b))
       = sum(a + b)

Of course that's assuming you don't want to do

sum(0) = 0
sum(n) = ((n - 1) % 9) + 1

Dan.



Fri, 07 Mar 2003 03:00:00 GMT  
 Help with "Cyclic Addition" function

Quote:

>There have been many interesting and informative suggestions as to
>various ways in which your task might be performed.  May I suggest,
>however, that it might be simpler and more efficient to simply
>do:
>    answer = input % 9

>since you evidently do have the modulo function available.

My bad.  One needs to handle the special cases (a) where the input is
0 (answer = 0) and (b) (input %9 == 0) where 9 is wanted.


http://www.*-*-*.com/
"It was half way to Rivendell when the {*filter*} began to take hold"
Hunter S Tolkien "Fear and Loathing in Barad Dur" - Iain Bowen



Fri, 07 Mar 2003 03:00:00 GMT  
 Help with "Cyclic Addition" function


Quote:

>This procedure is known as "casting out nines" and was widely taught
>and used as a technique for verifying calculations back in the dreary
>old days of the last millennium when people did arithmetic by hand.

>There have been many interesting and informative suggestions as to
>various ways in which your task might be performed.  May I suggest,
>however, that it might be simpler and more efficient to simply
>do:
>       answer = input % 9

>since you evidently do have the modulo function available.

Simpler, more efficient, and wrong 11% of the time AFAICS.

Modulo 9 gives an answer in 0..8, but one in 1..9 is needed (for
positive-definite numbers).

Perhaps         answer := Succ(Pred(Input) % 9) ;

--

 <URL: http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
 <URL: http://www.merlyn.demon.co.uk/clpb-faq.txt> Pedt Scragg: c.l.p.b. mFAQ;
 <URL: ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ.



Fri, 07 Mar 2003 03:00:00 GMT  
 Help with "Cyclic Addition" function
In comp.programming

Quote:

>My bad.  One needs to handle the special cases (a) where the input is
>0 (answer = 0) and (b) (input %9 == 0) where 9 is wanted.

This entire thread has been a monumental waste of everyone's time and the
reason is that we made a fundamental engineering mistake.  We failed to
find out WHAT the guy wanted to accomplish and simply gave him what he
asked for.  He wants a pseudorandom number generator.  Had I asked him why
he needed this sum of the digits algorithm and he answered as such, I would
point him to www.snippets.org where he will find source for several
pseudorandom number generators, some with periods that are simply
unimaginable.

Bruce



Sat, 08 Mar 2003 09:49:37 GMT  
 Help with "Cyclic Addition" function

Quote:

>This entire thread has been a monumental waste of everyone's time and the
>reason is that we made a fundamental engineering mistake.  We failed to
>find out WHAT the guy wanted to accomplish and simply gave him what he
>asked for.

Kinda true. I mostly thought it was a homework assignment
and try to walk him through how to approach this kind of
problem in general. Didn't realize what his intent was
until someone quoted the comment specifically.

Quote:
>He wants a pseudorandom number generator.  Had I asked him why
>he needed this sum of the digits algorithm and he answered as such, I would
>point him to www.snippets.org where he will find source for several
>pseudorandom number generators, some with periods that are simply
>unimaginable.

Given that the language already provides a pseudorandom
number generator, if he wants a number in certain range,
a simply modulo would have sufficed.

Dan.



Sat, 08 Mar 2003 13:43:47 GMT  
 
 [ 32 post ]  Go to page: [1] [2] [3]

 Relevant Pages 

1. Help with "Cyclic Addition" function

2. The keys "-"/"+"/"*"

3. ""256 Color Mouse""

4. "IsDate" Function for Delphi

5. A "NextFile" function

6. Weird "GotoXY" function problem

7. Help: "Help file to large"

8. Urgent, "Blob has been modified", Help...

9. HELP: "Error in Symbol File" message

10. Help finding "Console Application"

11. GOTO Command In Pascal "Need Help"

12. Need help with "Real"

 

 
Powered by phpBB® Forum Software