Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #260 > unrolled thread

Mystery program...

Back to article view | Back to comp.programming

Contents

  Mystery program... "Alf P. Steinbach /Usenet" <alf.p.steinbach+usenet@gmail.com> - 2011-05-02 00:10 +0200
    Re: Mystery program... Paul N <gw7rib@aol.com> - 2011-05-04 13:23 -0700
      Re: Mystery program... "io_x" <a@b.c.invalid> - 2011-05-05 09:02 +0200
        Re: Mystery program... "io_x" <a@b.c.invalid> - 2011-05-06 17:22 +0200
          Re: Mystery program... "io_x" <a@b.c.invalid> - 2011-05-07 09:12 +0200
          Re: Mystery program... "Alf P. Steinbach /Usenet" <alf.p.steinbach+usenet@gmail.com> - 2011-05-12 04:14 +0200
    Re: Mystery program... tm <thomas.mertes@gmx.at> - 2011-05-11 23:42 -0700
      Re: Mystery program... "Alf P. Steinbach /Usenet" <alf.p.steinbach+usenet@gmail.com> - 2011-05-12 14:17 +0200

#260 — Mystery program...

In my high-school "electronic data processing" text book from 1974 I found an 
"explain what this program does" exercise that I don't quite grok now.

It's exercise 4.25 from page 72 of "EDB for videregående skoler" by Gram, Hope 
and Ommundsen, NKS-forlaget 1974.

Here's the program translated from its original Basic to JavaScript (I'm 
assuming the Windows Script Host for i/o, and if  you have Windows simply copy 
this text to a [.js] file and run it via e.g. 'cscript' command):


<code>
lineNum_ = 0

function input()
{
     WScript.stdout.write( "? " );
     var s = WScript.stdin.readLine();
     return parseFloat( s );
}

function print( v )
{
     WScript.stdout.writeLine( v );
}

function goto( new_n )
{
     lineNum_ = new_n - 1
}

function end()
{
     print( "FINISHED!" )
     WScript.Quit()
}

function onStatementExecuted( lineNum )
{
     //print( "lineNum="+lineNum + ", n="+n + ", m="+m + ", p="+p + ", p2="+p2 )
}

m = null
n = null
p = null
p2 = null

for( ;; )
{
     lineNum_ += 1
     if( lineNum_ > 99999 )
     {
         print( "!Program execution beyond last statement." );
         WScript.Quit( -1 );
     }

     var executedLineNum = lineNum_
     var didSmth = true
     switch( lineNum_ )
     {
     case -1:

     // BEGIN translation of original code:
     break; case  30:    m = 1
     break; case  40:    n = input()
     break; case  50:    p2 = n
     break; case  60:    p = p2 - 2*m
     break; case  70:    p2 = p
     break; case  80:    m = m + 1
     break; case  90:    if( p < m ) goto( 140 )
     break; case 100:    p = p - m
     break; case 110:    if( p > 0 ) goto( 100 )
     break; case 120:    if( p == 0 ) goto( 160 )
     break; case 130:    if( p2 > 2*m ) goto( 60 )
     break; case 140:    print( "n=" + n );
     break; case 150:    goto( 170 )
     break; case 160:    print( "m=" + m )
     break; case 170:    end()
     // END translation of original code

     break; default:
         didSmth = false
     }

     if( didSmth )
     {
         onStatementExecuted( executedLineNum )
     }
}
</code>

The exercise's part (a) recommends trying out the program "on paper" (noting 
down values of variables) for n = 3, 10 and 28, and for part (b) it recommends 
running the program and trying n = 2, 14, 22, 36 and 39.

OK, I can see that there's apparently a computation of remainder in there, but 
it's not exactly meaningful to me.

I'm probably just blind on both eyes, but any help appreciated.


Cheers,

- Alf

-- 
blog at <url: http://alfps.wordpress.com>

[toc] | [next] | [standalone]

#269

On May 1, 11:10 pm, "Alf P. Steinbach /Usenet" <alf.p.steinbach
+use...@gmail.com> wrote:
> In my high-school "electronic data processing" text book from 1974 I found an
> "explain what this program does" exercise that I don't quite grok now.

>      // BEGIN translation of original code:
>      break; case  30:    m = 1
>      break; case  40:    n = input()
>      break; case  50:    p2 = n
>      break; case  60:    p = p2 - 2*m
>      break; case  70:    p2 = p
>      break; case  80:    m = m + 1
>      break; case  90:    if( p < m ) goto( 140 )
>      break; case 100:    p = p - m
>      break; case 110:    if( p > 0 ) goto( 100 )
>      break; case 120:    if( p == 0 ) goto( 160 )
>      break; case 130:    if( p2 > 2*m ) goto( 60 )
>      break; case 140:    print( "n=" + n );
>      break; case 150:    goto( 170 )
>      break; case 160:    print( "m=" + m )
>      break; case 170:    end()

I haven't cracked it completely, but I think I've essentially got it.
I haven't run it on a computer, but I tried "on paper" the following
values, which seemed more revealing than the ones suggested:

n = 3 -> n = 3
n = 10 -> m = 2
n = 28 -> m = 2
n = 2 -> n = 2
n = 14 -> m = 2
n = 39 -> m = 3

n = 5 -> n = 5
n = 7 -> n = 7
n = 25 -> m = 5

I think what it is is that, if n is prime, you get n = (inital value),
whereas if n is composite you get m = (lowest divider bigger than 1).

Looking at the program, there is a mini-loop at lines 100 and 110, but
apart from that, there is a main loop from lines 60 to 130, and the
program goes round that until it drops out at either 140 or 160.

n keeps its value. m goes up by 1 each time round the loop. p2 starts
at n but drops off slightly each time round. And p gets a new value
each time round the loop, it doesn't keep the old one.

Lines 100 and 110 find the remainder, but this remainder is not kept.
So in practice they simply check whether p is a multiple of m. Line
160 is triggered if p is a multiple of m; ie if p2 is a multiple of m.

Now, p2 is not the same as n. BUT this doesn't seem to matter. For
instance, if n is a multiple of 5 then so is n - 2 * (1+2+3+4) etc.So
although p2 is dropping in value, when we test whether it is a
multiple of m we are testing whether n is a multiple of m. But
slightly quicker.

Line 90 seems to be saying that, if p is less than m, then making m
bigger and/or p smaller is not going to make p a multiple of m until p
actually hits zero. Likewise line 130 seems to be saying that it's not
worth going back if p2 is too small. Presumably this only happens when
n is prime, but I'll leave this to you...

Hope this helps.
Paul.

[toc] | [prev] | [next] | [standalone]

#273

>"Paul N" ha scritto nel messaggio
>news:05f7402c-cf0d-4af2-b9a3->eef50af58041@y31g2000vbp.googlegroups.com...
>On May 1, 11:10 pm, "Alf P. Steinbach /Usenet" <alf.p.steinbach
>+use...@gmail.com> wrote:
>> In my high-school "electronic data processing" text book from 1974 I found an
>> "explain what this program does" exercise that I don't quite grok now.

;;
    at the start
    if n=3  b=3-2=1  1<2 esci
    this means that if input in range int_min..3 return "n=" +n
    not count the overflow for int_min etc

   if(n<=3)                  return print("n=" +n)
   else if((n-2)%2==0)       return print("m=" +2)
   else if((n-2-4)<3)        return print("n=" +n)
   else if((n-2-4)%3==0)     return print("m=" +2)
   else if((n-2-4-6)<4)      return print("n=" +n)
   else if((n-2-4-6)%4==0)   return print("m=" +4)
   else if((n-2-4-6-8)<5)    return print("n=" +n)
   else if((n-2-4-6-8)%5==0) return print("m=" +5)
   ...
;;

>> // BEGIN translation of original code:
>> break; case 30: m = 1
>> break; case 40: n = input()
>> break; case 50: p2 = n

>> break; case 60: p = p2 - 2*m
>> break; case 70: p2 = p
>> break; case 80: m = m + 1
>> break; case 90: if( p < m ) goto( 140 )

>> break; case 100: p = p - m
>> break; case 110: if( p > 0 ) goto( 100 )
>> break; case 120: if( p == 0 ) goto( 160 )
>> break; case 130: if( p2 > 2*m ) goto( 60 )
>> break; case 140: print( "n=" + n );
>> break; case 150: goto( 170 )
>> break; case 160: print( "m=" + m )
>> break; case 170: end()

    m=1|n=input()|b=n
.1: b=b-2*m|    ++m|b<m?#.3          ; m_ini=2
    a=b                              ; a=b=n-2
.2: a=a-m  |a>0?#.2|a==0#.4|b>2*m#.1 ; toglie 2 a n-2
.3: print("n=" +n)|#.9
.4: print("m=" +m)
.9:


>I haven't cracked it completely, but I think I've essentially got it.
>I haven't run it on a computer, but I tried "on paper" the following
>values, which seemed more revealing than the ones suggested:

>n = 3 -> n = 3
>n = 10 -> m = 2
>n = 28 -> m = 2
>n = 2 -> n = 2
>n = 14 -> m = 2
>n = 39 -> m = 3

>n = 5 -> n = 5
>n = 7 -> n = 7
>n = 25 -> m = 5

>I think what it is is that, if n is prime, you get n = (inital value),
>whereas if n is composite you get m = (lowest divider bigger than 1).

yes it is possible

[toc] | [prev] | [next] | [standalone]

#277

"io_x" <a@b.c.invalid> ha scritto nel messaggio
news:4dc24b67$0$18239$4fafbaef@reader2.news.tin.it...
> ;;
>    at the start
>    if n=3  b=3-2=1  1<2 esci
>    this means that if input in range int_min..3 return "n=" +n
>    not count the overflow for int_min etc
>
>   if(n<=3)                  return print("n=" +n)
>   else if((n-2)%2==0)       return print("m=" +2)
>   else if((n-2-4)<3)        return print("n=" +n)
>   else if((n-2-4)%3==0)     return print("m=" +2)
>   else if((n-2-4-6)<4)      return print("n=" +n)
>   else if((n-2-4-6)%4==0)   return print("m=" +4)
>   else if((n-2-4-6-8)<5)    return print("n=" +n)
>   else if((n-2-4-6-8)%5==0) return print("m=" +5)
>   ...
> ;;

and because Sum_i[0..n] i = n(n+1)/2
it is equivalent to
n=input()
for(m=2; m*(m-1)<=n ; ++m)
   if(n%m==0) {print("m=" m); return;}
print("n=" n);
return;
or
n=input()
for(m=2; m<=sqrt(n) ; ++m)
   if(n%m==0) {print("m=" m); return;}
print("n=" n);
return;

so print n if n is <=3 or prime; print m!=n if n%m==0

[toc] | [prev] | [next] | [standalone]

#278

"io_x" <a@b.c.invalid> ha scritto nel messaggio 
news:4dc411fe$0$38650$4fafbaef@reader1.news.tin.it...
> and because Sum_i[0..n] i = n(n+1)/2

Sum_i[1..n] i = n(n+1)/2

[toc] | [prev] | [next] | [standalone]

#305

* io_x, on 06.05.2011 17:22:
> "io_x"<a@b.c.invalid>  ha scritto nel messaggio
> news:4dc24b67$0$18239$4fafbaef@reader2.news.tin.it...
>> ;;
>>     at the start
>>     if n=3  b=3-2=1  1<2 esci
>>     this means that if input in range int_min..3 return "n=" +n
>>     not count the overflow for int_min etc
>>
>>    if(n<=3)                  return print("n=" +n)
>>    else if((n-2)%2==0)       return print("m=" +2)
>>    else if((n-2-4)<3)        return print("n=" +n)
>>    else if((n-2-4)%3==0)     return print("m=" +2)
>>    else if((n-2-4-6)<4)      return print("n=" +n)
>>    else if((n-2-4-6)%4==0)   return print("m=" +4)
>>    else if((n-2-4-6-8)<5)    return print("n=" +n)
>>    else if((n-2-4-6-8)%5==0) return print("m=" +5)
>>    ...
>> ;;
>
> and because Sum_i[0..n] i = n(n+1)/2
> it is equivalent to
> n=input()
> for(m=2; m*(m-1)<=n ; ++m)
>     if(n%m==0) {print("m=" m); return;}
> print("n=" n);
> return;
> or
> n=input()
> for(m=2; m<=sqrt(n) ; ++m)
>     if(n%m==0) {print("m=" m); return;}
> print("n=" n);
> return;
>
> so print n if n is<=3 or prime; print m!=n if n%m==0

Thanks to both of you, Paul and io_x.

Cheers,

- Alf


-- 
blog at <url: http://alfps.wordpress.com>

[toc] | [prev] | [next] | [standalone]

#307

On 2 Mai, 00:10, "Alf P. Steinbach /Usenet" <alf.p.steinbach
+use...@gmail.com> wrote:
> In my high-school "electronic data processing" text book from 1974 I found an
> "explain what this program does" exercise that I don't quite grok now.
>
> It's exercise 4.25 from page 72 of "EDB for videregående skoler" by Gram, Hope
> and Ommundsen, NKS-forlaget 1974.
>
> Here's the program translated from its original Basic to JavaScript

Why don't you execute the original BASIC program with a
BASIC interpreter?

Since it happnes that I wrote one, I suggest you try
Bas7. It is specialized towards BASIC programs from the
line number era of BASIC. See:

  http://seed7.sourceforge.net/scrshots/bas7.htm

Extracting the BASIC from your JavaScript gave:

30 m = 1
40 input n
50 p2 = n
60 p = p2 - 2*m
70 p2 = p
80 m = m + 1
90 if p < m then 140
100 p = p - m
110 if p > 0 then 100
120 if p = 0 then 160
130 if p2 > 2*m then 60
140 print "n="; n
150 goto 170
160 print "m="; m
170 end

I wrote 'then' instead of 'goto', but Bas7 would have
accepted 'goto' as well...
To see the output of the program i had to use the
option -p (prompt for a confirmation at the end of
the program):

  ./hi bas7 -p e_4_25.bas

With a few tests I could verify the result found by
Paul N.


Greetings Thomas Mertes

--
Seed7 Homepage:  http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

[toc] | [prev] | [next] | [standalone]

#310

* tm, on 12.05.2011 08:42:
> On 2 Mai, 00:10, "Alf P. Steinbach /Usenet"<alf.p.steinbach
> +use...@gmail.com>  wrote:
>> In my high-school "electronic data processing" text book from 1974 I found an
>> "explain what this program does" exercise that I don't quite grok now.
>>
>> It's exercise 4.25 from page 72 of "EDB for videregående skoler" by Gram, Hope
>> and Ommundsen, NKS-forlaget 1974.
>>
>> Here's the program translated from its original Basic to JavaScript
>
> Why don't you execute the original BASIC program with a
> BASIC interpreter?

It took less time to rewrite to JavaScript (just typing) than to find a suitable 
Basic interpreter (firing up browser, googling, downloading, bypassing Windows' 
inane "oops that file was downloaded, sure you want to use it?", etc.).

I first tried VBScript[1], though, but alas, it didn't accept line numbers or goto.


> Since it happnes that I wrote one, I suggest you try
> Bas7. It is specialized towards BASIC programs from the
> line number era of BASIC. See:
>
>    http://seed7.sourceforge.net/scrshots/bas7.htm
>

He he, thanks! :-)


Cheers,

- Alf


Notes:
[1] JScript and VBScript are the only general programming languages bundled with 
Windows.

-- 
blog at <url: http://alfps.wordpress.com>

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web