finding maximum


S

sandeep

Hello Friends ~

How would you find the maximum of
(a) two numbers
(b) a set of numbers
in idiomatic C? How would you do it in idiomatic Perl? Use this as a basis
for a discussion of the differences in expressive power of the two
languages.

Thx!

Sandeep
 
Ad

Advertisements

J

jacob navia

sandeep said:
Hello Friends ~

How would you find the maximum of
(a) two numbers
(b) a set of numbers
in idiomatic C? How would you do it in idiomatic Perl? Use this as a basis
for a discussion of the differences in expressive power of the two
languages.

Thx!

Sandeep

OK. To make it easier for you, can you tell us
the name of your teacher?

We will send him the answer directly.

thanks
 
P

Phil Carmody

sandeep said:
Hello Friends ~

How would you find the maximum of
(a) two numbers
(b) a set of numbers
in idiomatic C? How would you do it in idiomatic Perl? Use this as a basis
for a discussion of the differences in expressive power of the two
languages.

Can you let us have your teacher's email address, so that we
can get your homework answers to him directly, to save you the
effort.

Phil
 
D

Default User

sandeep said:
Hello Friends ~

How would you find the maximum of
(a) two numbers
(b) a set of numbers
in idiomatic C? How would you do it in idiomatic Perl? Use this as a
basis for a discussion of the differences in expressive power of the
two languages.

A better idea would be for you to do the homework that you've been
assigned. The assignment was for a reason, that is to teach you some
programming concepts and techniques.



Brian
 
S

sln

Hello Friends ~

How would you find the maximum of
(a) two numbers
(b) a set of numbers
in idiomatic C? How would you do it in idiomatic Perl? Use this as a basis
for a discussion of the differences in expressive power of the two
languages.

Thx!

Sandeep

What is "idiomatic" is that a washing machine gone bad?

-sln
 
S

Spiros Bousbouras

Can you let us have your teacher's email address, so that we
can get your homework answers to him directly, to save you the
effort.

Or perhaps it's flamebait disguised as homework.
 
Ad

Advertisements

T

Tad J McClellan

["Followup-To:" header set to comp.lang.perl.misc.]


Spiros Bousbouras said:
Or perhaps it's flamebait disguised as homework.


The poster's address should have been a big clue.

I have that one killfiled.
 
E

Eric Sosman

sandeep said:
Hello Friends ~

How would you find the maximum of
(a) two numbers

Negate both, find the minimum, and negate that minimum.
Be careful of corner cases: On many systems negating the most
negative integer fails to produce a positive integer (which
could lead to an incorrect answer), and on some systems there
are numbers X,Y such that X<=Y and Y<=X are *both* false.
A subtle problem; I wish you luck with it.
(b) a set of numbers

Much harder, because in a set of N numbers there are
(N choose 2) = N * (N-1) / 2 pairs to consider. Even for a
fairly modest set size like N = 1000000 it can easily happen
that (N choose 2) exceeds the maximum value of the system's
integer.

So, I suggest a heuristic approach. Choose a pair of the
numbers at random, and determine their maximum by applying the
solution to (a). Then choose another pair at random and find
*their* maximum the same way. Now (and here's the crux) you
have formed the leftmost two pieces of a tree in which all the
numbers appear:

. .
. . .
/ \ .
max(A,B) max(C,D) .
/ \ / \ /
A B C D E ...

Using a stack (or possibly a priority queue) you can recursively
compute max(A,B,C,D) = max(max(A,B), max(C,D)), and then
max(A,B,C,D,E,F,G,H) = max(max(A,B,C,D), max(E,F,G,H))
= max(max(max(A,B), max(C,D)), max(max(E,F), max(G,H))) and
so on, populating the tree in a bottom-up left-to-right
fashion. Eventually, the root of the tree will be equal to the
maximum of the entire set, with a probability close to unity.
There's a strong analogy to the Mergesort algorithm: If you
consider the tree as a representation of a merge sort, then
the desired maximum of N elements is the unique element that
is not among the first N-1 emitted.
in idiomatic C?

There is no such thing as "idiomatic C." There are only
"High C" (as practiced during the High C Era), and "Trade C"
(the patois that has taken hold among those who'd rather get
things done than argue about the proprieties). There are also
some debased C-ish dialects, notably "Rapper's C" or "CRap."
How would you do it in idiomatic Perl?

Ah! A much easier question! Answer: I would not do it
in any kind of Perl, idiotmatic or otherwise.
Use this as a basis
for a discussion of the differences in expressive power of the two
languages.

Both languages are Turing-complete, that is, capable of
expressing methods that solve all computable functions (subject
to the finiteness limits of the computers they execute on.) Also,
both languages are Virgil-complete, that is, capable of expressing
figurative and poetic thought, as in

C2shining(C)

and

Perl + Perl <- Swine

D'rn.
 
T

Tad J McClellan

["Followup-To:" header set to comp.lang.perl.misc.]


Eric Sosman said:
sandeep wrote:

There is no such thing as "idiomatic C." There are only
"High C" (as practiced during the High C Era), and "Trade C"
(the patois that has taken hold among those who'd rather get
things done than argue about the proprieties). There are also
some debased C-ish dialects, notably "Rapper's C" or "CRap."


Leaving out "Tenne C" is inexcusable.

http://www.netfunny.com/rhf/jokes/88q3/0tenny.html
 
A

Andrey Vul

     Negate both, find the minimum, and negate that minimum.
Be careful of corner cases: On many systems negating the most
negative integer fails to produce a positive integer (which
could lead to an incorrect answer), and on some systems there
are numbers X,Y such that X<=Y and Y<=X are *both* false.
A subtle problem; I wish you luck with it.


     Much harder, because in a set of N numbers there are
(N choose 2) = N * (N-1) / 2 pairs to consider.  Even for a
fairly modest set size like N = 1000000 it can easily happen
that (N choose 2) exceeds the maximum value of the system's
integer.

     So, I suggest a heuristic approach.  Choose a pair of the
numbers at random, and determine their maximum by applying the
solution to (a).  Then choose another pair at random and find
*their* maximum the same way.  Now (and here's the crux) you
have formed the leftmost two pieces of a tree in which all the
numbers appear:

              .      .
             .        .            .
            /          \          .
        max(A,B)    max(C,D)     .
         /   \       /   \      /
        A     B     C     D    E    ...

Using a stack (or possibly a priority queue) you can recursively
compute max(A,B,C,D) = max(max(A,B), max(C,D)), and then
max(A,B,C,D,E,F,G,H) = max(max(A,B,C,D), max(E,F,G,H))
= max(max(max(A,B), max(C,D)), max(max(E,F), max(G,H))) and
so on, populating the tree in a bottom-up left-to-right
fashion.  Eventually, the root of the tree will be equal to the
maximum of the entire set, with a probability close to unity.
There's a strong analogy to the Mergesort algorithm: If you
consider the tree as a representation of a merge sort, then
the desired maximum of N elements is the unique element that
is not among the first N-1 emitted.


     There is no such thing as "idiomatic C."  There are only
"High C" (as practiced during the High C Era), and "Trade C"
(the patois that has taken hold among those who'd rather get
things done than argue about the proprieties).  There are also
some debased C-ish dialects, notably "Rapper's C" or "CRap."


     Ah!  A much easier question!  Answer: I would not do it
in any kind of Perl, idiotmatic or otherwise.


     Both languages are Turing-complete, that is, capable of
expressing methods that solve all computable functions (subject
to the finiteness limits of the computers they execute on.)  Also,
both languages are Virgil-complete, that is, capable of expressing
figurative and poetic thought, as in

        C2shining(C)

and

        Perl + Perl <- Swine

 > Thx!

     D'rn.


You have made my day. Thank you so much.
 
S

sln

[I note that the OP has not yet had any responses that move him
forward technically (nice try, though, Eric!). So the first part of
this response is a token effort in that direction.]

sandeep said:
Hello Friends ~

How would you find the maximum of
(a) two numbers

Use the comparison operator.
(b) a set of numbers

Store the first number in the set, making it the "current maximum".
Then use the comparison operator in a loop, updating the current
maximum whenever appropriate.
in idiomatic C?

See above.
How would you do it in idiomatic Perl?

Well, personally I wouldn't do it in Perl, but no doubt the fine
folks in comp.lang.perl.misc /would/ do it in Perl, and that is
their right and privilege.
Use this as
a basis for a discussion of the differences in expressive power of
the two languages.

C is expressively powerful, whereas Perl is powerfully expressive.

Pretty lose language. Can you give examples of that?

-sln
 
Ad

Advertisements

S

sln

(e-mail address removed) said:


That's wonderfully self-referential. Thanks for the smile.


See IOCCC for examples of expressively powerful C. See CPAN for
examples of expressively powerful Perl.

Why don't you 'C' a doctor for examples.

-sln
 
J

Josef Moellers

sandeep said:
Hello Friends ~

How would you find the maximum of
(a) two numbers
(b) a set of numbers
in idiomatic C? How would you do it in idiomatic Perl? Use this as a basis
for a discussion of the differences in expressive power of the two
languages.

The simple answer is: "Post the problem to the usenet and wait for
others to solve it for you".
 
T

Ted Zlatanov

s> How would you find the maximum of
s> (a) two numbers
s> (b) a set of numbers
s> in idiomatic C? How would you do it in idiomatic Perl?

In any language, you put the numbers in an array, sort the array, and
return the element at the top. Similarly, to get the average, you sort
the array and then return the middle number (AKA the "median average").

In Perl sorting is even built into the language; in C unfortunately you
have to embed the Perl interpreter to get that kind of simplicity.

s> Use this as a basis for a discussion of the differences in expressive
s> power of the two languages.

We are programmers, sir. Discussion does not become us. We are always
right, even when we're wrong.

Ted
 
S

sandeep

Friends ~

Thanks for the answers. Actually this is not a homework, I am just curious.

Anyways, here is my solution:

(a) in C:

int max(int a, int b)
{
if(a>b)
return a;
return b;
}

in Perl:

sub max
{
my $max = shift;
for(@_) {
$max=$_ if($_>$max)
}
$max;
}


(b) in C:

#define NUMMAX (10)
int max(int a[NUMMAX])
{
int max = -1;
for(int i=0; i < NUMMAX;)
if(a[i++]>max)
max = a[i-1];
return max;
}


In Perl: the solution for (a) still works.

Conclusion: Perl is more expressive as a simple function for two arguments
often generalizes to any list.

Best greetings
Sandeep
 
Ad

Advertisements

U

user923005

Friends ~

Thanks for the answers. Actually this is not a homework, I am just curious.

Anyways, here is my solution:

(a) in C:

int max(int a, int b)
{
  if(a>b)
    return a;
  return b;

}

in Perl:

sub max
{
  my $max = shift;
  for(@_) {
    $max=$_ if($_>$max)
  }
  $max;

}

(b) in C:

#define NUMMAX (10)
int max(int a[NUMMAX])
{
  int max = -1;
  for(int i=0; i < NUMMAX;)
    if(a[i++]>max)
       max = a[i-1];
  return max;

}

In Perl: the solution for (a) still works.

Conclusion: Perl is more expressive as a simple function for two arguments
often generalizes to any list.

If performance matters, C will probably be a little faster.
If your programmers who maintain the code are Perl programmers, then
Perl is the logical choice, and vice-versa.
In either case, unless you are processing a billion items, the
language choice does not matter much.
If a language is Turing complete (and most of them are) then something
simple like finding the max from a list can be done without much fuss.

Which language to choose to solve some programming problem usually
turns into a pissing match, especially when cross-posted to multiple
language groups.

For my opinion, I don't think either one is a better choice.

IMO-YMMV
 
M

Martin Ambuhl

sandeep said:
Friends ~

Thanks for the answers. Actually this is not a homework, I am just curious.

Anyways, here is my solution:

all of which are verbose compared to (max list):
>;; maximum of one integer
(max 3)
3
;; maximum of two integers
(max 483 6932487534)
6932487534
;; maximum of two floats and an integer
(max 4.72 49.1 -3)
49.100000000000001
;; maximum of a list, including several types
(max -3 49/3 5.37s-1 -34.3l-2 5.1)
49/3
;; minimum of the same list
(min -3 49/3 5.37s-1 -34.3l-2 5.1)
-3
> ;; print value of the list
>'(-3 49/3 5.37s-1 -34.3l-2 5.1)
(-3 49/3 0.537S0 -0.34299999999999997 5.0999999999999996)
Conclusion: Perl is more expressive as a simple function for two arguments
often generalizes to any list.

Conclusion: lisp is more expressive, period.
 
J

jameskuyper

Ted said:
s> How would you find the maximum of
s> (a) two numbers
s> (b) a set of numbers
s> in idiomatic C? How would you do it in idiomatic Perl?

In any language, you put the numbers in an array, sort the array, and
return the element at the top. Similarly, to get the average, you sort
the array and then return the middle number (AKA the "median average").

That's at best an O(N log N) solution. There's an O(N) solution which
is even simpler; sandeep presented the basic idea for that solution
(badly) in his second message on this thread.
In Perl sorting is even built into the language; in C unfortunately you
have to embed the Perl interpreter to get that kind of simplicity.

In C, sorting is built into the standard library: qsort(). It may be
clumsier to use, perhaps, than Perl's sort, but it's still an easier
solution for a C program than embedding the perl interpreter.
 
Ad

Advertisements

T

Tad J McClellan

["Followup-To:" header set to comp.lang.perl.misc.]


Ted Zlatanov said:
s> How would you find the maximum of
s> (a) two numbers
s> (b) a set of numbers
s> in idiomatic C? How would you do it in idiomatic Perl?

In any language, you put the numbers in an array, sort the array, and
return the element at the top.


Unless the array might be "large".

Your algorithm is likely O(n log n) when finding the maximum can
be done in only O(n).

s> Use this as a basis for a discussion of the differences in expressive
s> power of the two languages.

We are programmers, sir. Discussion does not become us.


Sure we do. We discuss stuff all the time.

But we discuss what interests us.

That is, we do not take direction from random usenauts.
 

Top