Most efficient way to find the greatest of three ints

Question

Below is my pseudo code.

function highest(i, j, k)
{
  if(i > j && i > k)
  {
    return i;
  }
  else if (j > k)
  {
    return j;
  }
  else
  {
    return k;
  }
}

I think that works, but is that the most efficient way in C++?

Wildfowl

Could you use this at all? cplusplus.com/reference/algorithm/max – Kassia

In this case if it is homework, it's OK, since the questioner has made an attempt, shown his code and is asking for improvement. That meets all the guidelines for posting homework questions on SO. – Bridgework

@ Robert Greiner ha ha, no. though it would make a great homework question, no? – Wildfowl

This is more a question of efficient. I know this will give me the right answer, but as a programmer, how do I know I'm doing it quickly and efficiently? – Wildfowl

@Bridgework Never said it wasn't a valid question. – Rayfordrayle

@Stephano: You profile it and determine if it's the main slow-down in your program. It's a common error to worry about the efficiency of everything; just make the code easy to understand and easy to write, and let the compiler do it's part. – Robin

Here's the most efficient way possible: /* Precondition: i is the largest value of the three. */ int max(int i, int j, int k) { return i; } or possibly just return 42. – Gony

@GMan good point. i guess i'm just hoping to be a better mathematical programmer. i'm probably just making up for my lack of math classes ;) . – Wildfowl

Answer 1

To find the greatest you need to look at exactly 3 ints, no more no less. You're looking at 6 with 3 compares. You should be able to do it in 3 and 2 compares.

int ret = max(i,j);
ret = max(ret, k);
return ret;

Uropod

Could make a nice little function: template <typename T> const T& max(const T& pA, const T& pB, const T& pC){ return max(pA, max(pB, pC)); } – Robin

max(i, max(j, k)) saves it to one line. I like the template version too – Serration

the stl defines that, doesn't it? Would be a good thing to use. – Uropod

Of course, if max is a macro or an inline function, max(i, max(j, k)) is going to expand to something along the lines of i > ( j > k ? j : k ) ? i : ( j > k ? j : k ) (CSE optimization notwithstanding) and if it isn't, you have function call overhead. Are we talking about programmer efficiency or computational efficiency? – Chantay

You're assuming that max is built into the hardware at the same cost as a comparison. What machine are you using? – Halfwit

@Duncan: You're wrong about when it's an inline function, and since this question is C++, we're talking about std::max. A macro named 'max' is, in C++, pure abomination. – Catalyst

@Roger Pate: Macros are an abomination even in C :). Perhaps I should have said "..a template or inline ...." So what happens for an inline expression? Surely that will inline to something like rv1 = j > k ? j : k; rv2 = i > rv1 ? i : rv1; return rv2; which is the same thing only with CSE. Have I missed something? Perhaps things have changed in the 2 decades since I last bothered looking at generated assembly language. I don't mind being told I'm wrong, though I do prefer to be told why :) – Chantay

@Duncan, @Chris: let's call it std::max and be through with it. @Chris: GNU STL defines median as a private function, maybe that's what you're thinking of. – Streetwalker

But isn't accessing ret in the second line considered another "looking", which makes it 4 instead of 3? – Best

@Duncan: I interpreted you as using macro expansion in both and relying on CSE to clean it up, versus how the semantics of inline functions (even inline functions in C) mean CSE doesn't even apply (you no longer have a common expression); and I can see how you meant other than what I read earlier. – Catalyst

I think Ignacio's code was more straight forward, but your explanation at the top takes the cake. Well put. – Wildfowl

Answer 2

Pseudocode:

result = i
if j > result:
  result = j
if k > result:
  result = k
return result

Conquian

Excellent! Very clear, and makes it very likely that if the hardware has predicated instructions like cmov, the compiler will use them. +1 (wish I could +10 past the evil max) – Halfwit

Answer 3

How about

return i > j? (i > k? i: k): (j > k? j: k);

two comparisons, no use of transient temporary stack variables...

Hanzelin

Answer 4

Your current method: http://ideone.com/JZEqZTlj (0.40s)

Chris's solution:

int ret = max(i,j);
ret = max(ret, k);
return ret;

http://ideone.com/hlnl7QZX (0.39s)

Solution by Ignacio Vazquez-Abrams:

result = i;
if (j > result)
  result = j;
if (k > result)
  result = k;
return result;

http://ideone.com/JKbtkgXi (0.40s)

And Charles Bretana's:

return i > j? (i > k? i: k): (j > k? j: k);

http://ideone.com/kyl0SpUZ (0.40s)

Of those tests, all the solutions take within 3% the amount of time to execute as the others. The code you are trying to optimize is extremely short as it is. Even if you're able to squeeze 1 instruction out of it, it's not likely to make a huge difference across the entirety of your program (modern compilers might catch that small optimization). Spend your time elsewhere.

EDIT: Updated the tests, turns out it was still optimizing parts of it out before. Hopefully it's not anymore.

Emmerich

ok, I'm (slightly) happier with the updated version. SO won't let me remove the -1 though ("Vote too old to be changed, unless this answer is edited"), sorry. – Flypaper

Wow, sweet. I had no idea ideone existed. this gives me something to do when I can't sleep :) . – Wildfowl

Answer 5

For a question like this, there is no substitute for knowing just what your optimizing compiler is doing and just what's available on the hardware. If the fundamental tool you have is binary comparison or binary max, two comparisons or max's are both necessary and sufficient.

I prefer Ignacio's solution:

result = i;
if (j > result)
  result = j;
if (k > result)
  result = k;
return result;

because on the common modern Intel hardware, the compiler will find it extremely easy to emit just two comparisons and two cmov instructions, which place a smaller load on the I-cache and less stress on the branch predictor than conditional branches. (Also, the code is clear and easy to read.) If you are using x86-64, the compiler will even keep everything in registers.

Note you are going to be hard pressed to embed this code into a program where your choice makes a difference...

Halfwit

Answer 6

I like to eliminate conditional jumps as an intellectual exercise. Whether this has any measurable effect on performance I have no idea though :)

#include <iostream>
#include <limits>

inline int max(int a, int b)
{
    int difference = a - b;
    int b_greater = difference >> std::numeric_limits<int>::digits;
    return a - (difference & b_greater);
}

int max(int a, int b, int c)
{
    return max(max(a, b), c);
}

int main()
{
    std::cout << max(1, 2, 3) << std::endl;
    std::cout << max(1, 3, 2) << std::endl;
    std::cout << max(2, 1, 3) << std::endl;
    std::cout << max(2, 3, 1) << std::endl;
    std::cout << max(3, 1, 2) << std::endl;
    std::cout << max(3, 2, 1) << std::endl;
}

This bit twiddling is just for fun, the cmov solution is probably a lot faster.

Decretory

Answer 7

Not sure if this is the most efficient or not, but it might be, and it's definitely shorter:

int maximum = max( max(i, j), k);

Toomey

Answer 8

There is a proposal to include this into the C++ library under N2485. The proposal is simple, so I've included the meaningful code below. Obviously, this assumes variadic templates

template < typename T >
const T & max ( const T & a )
{ return a ; }

template < typename T , typename ... Args >
const T & max( const T & a , const T & b , const Args &... args )
{ return  max ( b > a ? b : a , args ...); }

Solanaceous

Answer 9

The easiest way to find a maximum or minimum of 2 or more numbers in c++ is:-

int a = 3, b = 4, c = 5;
int maximum = max({a, b, c});

int a = 3, b = 4, c = 5;
int minimum = min({a, b, c});

You can give as many variables as you want.

Interestingly enough it is also incredibly efficient, at least as efficient as Ignacio Vazquez-Abrams'solution (https://godbolt.org/z/j1KM97):

        mov     eax, dword ptr [rsp + 8]
        mov     ecx, dword ptr [rsp + 4]
        cmp     eax, ecx
        cmovl   eax, ecx
        mov     ecx, dword ptr [rsp]
        cmp     eax, ecx
        cmovl   eax, ecx

Similar with GCC, while MSVC makes a mess with a loop.

Govan

It's defined in the header file <algorithm> as template constexpr T max (initializer_list il, Compare comp); – Foxhole

Answer 10

public int maximum(int a,int b,int c){
    int max = a;
    if(b>max)
        max = b;
    if(c>max)
        max = c;
    return max;
}

Semeiology

Answer 11

I think by "most efficient" you are talking about performance, trying not to waste computing resources. But you could be referring to writing fewer lines of code or maybe about the readability of your source code. I am providing an example below, and you can evaluate if you find something useful or if you prefer another version from the answers you received.

/* Java version, whose syntax is very similar to C++. Call this program "LargestOfThreeNumbers.java" */
class LargestOfThreeNumbers{
    public static void main(String args[]){
        int x, y, z, largest;
        x = 1;
        y = 2;
        z = 3;
        largest = x;
        if(y > x){
            largest = y;
            if(z > y){
                largest = z;
            }
        }else if(z > x){
            largest = z;
        }
        System.out.println("The largest number is: " + largest);
    }
}

Armanda

Answer 12

#include<stdio.h>
int main()
{
    int a,b,c,d,e;
    scanf("%d %d %d",&a,&b,&c);
    d=(a+b+abs(a-b))/2;
    e=(d+c+abs(c-d))/2;
    printf("%d is Max\n",e);
    return 0;
}

Huehuebner

Answer 13

I Used This Way, It Took 0.01 Second

#include "iostream"
using std::cout;
using std::cin;
int main()
{
    int num1, num2, num3;
    cin>>num1>>num2>>num3;
    int cot {((num1>num2)?num1:num2)};
    int fnl {(num3>cot)?num3:cot};
    cout<<fnl;
}

Or This

#include "iostream"

using std::cout;
using std::cin;
int main()
{
    int num1, num2, num3;
    cin>>num1>>num2>>num3;
    int cot {(((num1>num2)?num1:num2)>((num3>cot)?num3:cot)?((num1>num2)?num1:num2):((num3>cot)?num3:cot))};
    cout<<cot;
}

Divisible

Answer 14

The most efficient way to find the greatest among 3 numbers is by using max function. Here is a small example:

#include <iostream>
#include <algorithm>

using namespace std;
int main() {
   int x = 3, y = 4, z = 5;
   cout << max(x, max(y, z)) << endl;
   return 0;
}

If you have C++ 11, then you can do it as follow:

int main() {
   int x = 3, y = 4, z = 5;
   cout << std::max({x, y, z}); << endl;
   return 0;
}

If you are interested to use a function, so that you can call it easily multiple times, here is the code:

using namespace std;

int test(int x, int y, int z) { //created a test function

    //return std::max({x, y, z}); //if installed C++11
    return max(x, max(y, z));
}

int main() {
    cout << test(1, 2, 3) << endl;
    cout << test(1, 3, 2) << endl;
    cout << test(1, 1, 1) << endl;
    cout << test(1, 2, 2) << endl;
    return 0;
}

Sleepyhead

Answer 15

Here is a small function you can use:

int max3(int a, int b, int c=INT_MIN) {
    return max(a, max(b, c));
}

Masterful

Answer 16

In C# finding the greatest and smallest number between 3 digit

static void recorrectFindSmallestNumber()
{
int x = 30, y = 22, z = 11;
if (x < y)
{
if (x < z)
{
Console.WriteLine("X is Smaller Numebr {0}.", x);
}
else
{
Console.WriteLine("z is Smaller Numebr {0}.", z);
}
}
else if (x > y)
{
if (y < z)
{
Console.WriteLine("y is Smaller number.{0}", y);
}
else
{
Console.WriteLine("z is Smaller number.{0}", z);
}
}
 else
{

}
}

=================================================================

static void recorrectFindLargeNumber()
{
int x, y, z;
Console.WriteLine("Enter the first number:");
x = int.Parse(Console.ReadLine());
Console.WriteLine("Enter the second number:");
y = int.Parse(Console.ReadLine());
Console.WriteLine("Enter the third nuumnber:");
z = int.Parse(Console.ReadLine());
if (x > y)
{
if (x > z)
{
Console.WriteLine("X is Greater numbaer: {0}.", x);
}
else
{
Console.WriteLine("Z is greatest number: {0}.", z);
}
}
else if (x < y)
{
if (y > z)
{
Console.WriteLine("y is Greater Number: {0}", y);
}
else 
{
Console.WriteLine("Z is Greater Number; {0}", z);                
}
}
else
{
                
}
}

Marron

Answer 17

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int num1,num2,num3,maximum;

cout<<"Enter 3 numbers one by one "<<endl;
cin>>num1;
cin>>num2;
cin>>num3;

maximum=max(max(num1,num2),num3);

cout<<"maximum of 3 numbers is "<<maximum<<endl;
}

Appurtenant

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Turro