Quiz

Learn or Teach General Knowledge Related to Coding or Hacking

Moderators: g3nuin3, SpeedWing, WhiteHat, mezzo

Quiz

Postby L. Spiro » Fri Dec 04, 2009 3:56 pm

I will post several snippets of code in C++. Most of the problems here have nothing to do with the actual language being used and this is not a syntax/be-sure-everything-was-declared set of questions.
The floating-point numbers are completely arbitrary and have no meaning in this quiz. The integral numbers can be assumed significant to the solutions.

Each of these snippets is wrong.
Your objective is to rewrite them so that they are correct.
Anyone may try (if your attempts are serious), however only the most advanced of coders will actually find the correct answers.

In order to relax your minds, I will tell you not to waste your time looking at the subtle details such as using :: scoping on global functions or using UL after numbers to indicate their signs and sizes.
Additionally, you can assume the types of values based on prefixes.
f = float.
st = size_t.
i = int.
d = double.
ul = unsigned long.


#1: Solved first by troublesh00ter.
Code: Select all
CUtils::CallFunction( fX / 16.0f, fY / 16.0f );


#2: Solved first by CoMPMStR.
Code: Select all
vVec.x = ::cos( fA );
vVec.y = -::sin( fA );
vVec.z = ::sin( fA );


#3: Solved first by CoMPMStR.
Code: Select all
for ( int I = static_cast<int>(vVector.size() - 1UL); I >= 0; --I ) {
   // Do whatever.
}


#4: Solved first by CoMPMStR.
Code: Select all
// Our objective here is ONLY to get the maximum value in a vector of unsigned longs.
unsigned long ulMax = 0UL;
for ( size_t I = 0UL; I < vVector.size(); ++I ) {
    ulMax = std::max( ulMax, vVector[I] );
}


#5: Solved first by CoMPMStR.
Code: Select all
++ulSwitch;
ulSwitch %= 2UL;


#6: Solved first by CoMPMStR.
Code: Select all
ulX = ulIndex % 16UL;
ulY = ulIndex / 16UL;


#7: Solved first by CoMPMStR.
Code: Select all
for ( int I = 0; I < iTotal; ++I ) {
    // Do something.
}



L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby troublesh00ter » Sat Dec 05, 2009 5:58 am

When you say 'wrong' I guess you don't always mean that the result is incorrect - but also that it can be done better/faster?

#1:
Code: Select all
// Dividing (especially floats) is slow
CUtils::CallFunction( fX * 0.0625f, fY * 0.0625f );


#2:
Code: Select all
vVec.x = ::cos( fA );
vVec.y = -::sin( fA );
vVec.z = -vVec.y;          // No need to call sin() twice


#4:
Code: Select all
// No elements in the vector are destroyed/created.. so the size is constant
// leaving .size() in the for loop will mean it gets called on every iteration
unsigned long ulVecSize = vVector.size();
for ( size_t I = 0UL; I < ulVecSize; ++I ) {
    ulMax = std::max( ulMax, vVector[I] );
}


#5:
Code: Select all
ulSwitch = 0;        // Don't really see what's wrong with this one...
// Guess it had something to do with left-to-right and right-to-left.. but I thought that only mattered if you
// combine expressions like: y = x / ++x;
// Ran the following snippet for a while and it never broke the loop.
// Or is it in fact a left-to-right problem and am I just lucky that my compiler does it right?
while( true )
{
    ++ulSwitch;
    ulSwitch %= 2UL;
    if( ulSwitch != ! ulLastResult )
        break;
    ulLastResult = ulSwitch;
}
printf( "ulSwitch %u\n", ulSwitch );


#6:
Code: Select all
ulY = ulIndex / 16UL;            // % is unnecessary if we also need the division
ulX = ulIndex - ulY * 16UL;
troublesh00ter
Sir Hacks-A-Lot
 
Posts: 30
Joined: Mon Jun 01, 2009 2:54 pm
Location: The Netherlands

Re: Quiz

Postby cobr_h » Sat Dec 05, 2009 6:05 am

troublesh00ter wrote:When you say 'wrong' I guess you don't always mean that the result is incorrect - but also that it can be done better/faster?


this clarifies things a lot
cobr_h
Acker
 
Posts: 72
Joined: Wed Dec 02, 2009 6:15 am

Re: Quiz

Postby CoMPMStR » Sat Dec 05, 2009 6:34 am

#3:
Code: Select all
int iSize = static_cast<int>(vVector.size() - 1UL);
for ( int I = iSize; I >= 0; --I ) {
   // Do whatever.
}


or

Code: Select all
int iSize = vVector.size() - 1;
for ( int I = iSize; I >= 0; --I ) {
   // Do whatever.
}
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby cobr_h » Sat Dec 05, 2009 6:44 am

if it is for performance, I think:

for #4 I would

Code: Select all
unsigned long ulMax = 0UL;
for ( size_t I = (sizeof(vVector)/sizeof(unsigned long))-1; I > 0; --I ) {
    ulMax = std::max( ulMax, vVector[I] );
}


no more memory used and not a lot of calculations done. in the end it's the same solution proposed by troubleshooter.
And I have considered that, if you wanna call vVector with brackets, it is not supposed to have any method... or else it would be an vector of objects. Did I take in consideration subtle detail? :)

and #5 could:
Code: Select all
ulSwitch=!ulSwitch;

As I really have seen in a code around (tutorials or so).
cobr_h
Acker
 
Posts: 72
Joined: Wed Dec 02, 2009 6:15 am

Re: Quiz

Postby L. Spiro » Sat Dec 05, 2009 9:19 am

troublesh00ter wrote:When you say 'wrong' I guess you don't always mean that the result is incorrect - but also that it can be done better/faster?

#1:
Code: Select all
// Dividing (especially floats) is slow
CUtils::CallFunction( fX * 0.0625f, fY * 0.0625f );

This is a 90% answer, but the concept behind the question has been solved.
The 100% answer is:
Code: Select all
CUtils::CallFunction( (1.0f / 16.0f) * fX, (1.0f / 16.0f) * fY );

Rule #1: Put the constants to the left of the variable. This guarantees that the compiler will perform the division at compile-time even if you forget the parentheses.
Rule #2: Use parentheses anyway. It makes it clear to viewers that that constant will be evaluated by itself, and ensures no complications with other multiplications or divisions.
Rule #3: Use the long form of 1.0f / 16.0f instead of just using the constant 0.0625f. This allows everyone to easily determine how the constant was derived and allows them to easily reconsider the problem as a division rather than a multiplication of an arbitrary number.



troublesh00ter wrote:#2:
Code: Select all
vVec.x = ::cos( fA );
vVec.y = -::sin( fA );
vVec.z = -vVec.y;          // No need to call sin() twice


Is there something more you can do to this?



troublesh00ter wrote:#4:
Code: Select all
// No elements in the vector are destroyed/created.. so the size is constant
// leaving .size() in the for loop will mean it gets called on every iteration
unsigned long ulVecSize = vVector.size();
for ( size_t I = 0UL; I < ulVecSize; ++I ) {
    ulMax = std::max( ulMax, vVector[I] );
}


That is one good idea, but is there a better way to go about this?



troublesh00ter wrote:#5:
Code: Select all
[/quote]
ulSwitch = 0;        // Don't really see what's wrong with this one...
// Guess it had something to do with left-to-right and right-to-left.. but I thought that only mattered if you
// combine expressions like: y = x / ++x;
// Ran the following snippet for a while and it never broke the loop.
// Or is it in fact a left-to-right problem and am I just lucky that my compiler does it right?
while( true )
{
    ++ulSwitch;
    ulSwitch %= 2UL;
    if( ulSwitch != ! ulLastResult )
        break;
    ulLastResult = ulSwitch;
}
printf( "ulSwitch %u\n", ulSwitch );


Your loop will never break because the code is doing the same thing as ulSwitch = !ulSwitch.
Is there a better way to write this?



troublesh00ter wrote:#6:
Code: Select all
ulY = ulIndex / 16UL;            // % is unnecessary if we also need the division
ulX = ulIndex - ulY * 16UL;


I am afraid this is incorrect.





CoMPMStR wrote:#3:
Code: Select all
int iSize = static_cast<int>(vVector.size() - 1UL);
for ( int I = iSize; I >= 0; --I ) {
   // Do whatever.
}


or

Code: Select all
int iSize = vVector.size() - 1;
for ( int I = iSize; I >= 0; --I ) {
   // Do whatever.
}


I am afraid that each of these is at least as problematic as the original snippets.





cobr_h wrote:if it is for performance, I think:

for #4 I would

Code: Select all
unsigned long ulMax = 0UL;
for ( size_t I = (sizeof(vVector)/sizeof(unsigned long))-1; I > 0; --I ) {
    ulMax = std::max( ulMax, vVector[I] );
}


no more memory used and not a lot of calculations done. in the end it's the same solution proposed by troubleshooter.
And I have considered that, if you wanna call vVector with brackets, it is not supposed to have any method... or else it would be an vector of objects. Did I take in consideration subtle detail? :)


The original snippet used a vector class, which would of course give you some troubles if you were to apply the sizeof() operator in this manner; however, as stated, this solution only uses the vector class as an example, and you are indeed free to change it to a regular array in your answer. This is, however, not part of the answer.

On the brighter side, you did get a 50% score for another reason. Can you finish it off for the final 100%?



cobr_h wrote:
Code: Select all
ulSwitch=!ulSwitch;

As I really have seen in a code around (tutorials or so).


This is very superior over the code in the original snippet.
Is there a better way to write this?


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby x4NG3L » Sun Dec 06, 2009 3:41 am

I DONT code in C++ !
I Code in VB
More i Go Try, Only for Fun.


My #2:
Code: Select all
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

struct vVec
{
  float x;
  float y;
  float z;
};


int main ()
{

double fA;
vVec.x = cos(fA);
vVec.y = sin(fA);
vVec.z = sin(fA);
printf ("Is This?");

  return 0;
}




My #3:

Code: Select all
#include <iostream>
#include <vector>
using namespace std;


int main ()
{

vector<int> vVector;


int I;
for(I = static_cast<int>(vVector.size() - 1UL); I >= 0; I )
{
  printf ("Is This?" );
}

  return 0;
}
Last edited by x4NG3L on Sun Dec 06, 2009 4:42 am, edited 1 time in total.
Knowledge is evolving.
User avatar
x4NG3L
Sir Hacks-A-Lot
 
Posts: 31
Joined: Fri Nov 20, 2009 5:20 am

Re: Quiz

Postby troublesh00ter » Sun Dec 06, 2009 4:10 am

L. Spiro wrote:
troublesh00ter wrote:#2:
Code: Select all
vVec.x = ::cos( fA );
vVec.y = -::sin( fA );
vVec.z = -vVec.y;          // No need to call sin() twice


Is there something more you can do to this?


I've been trying to come up with ways to calculate cos and sin from one call. But I failed to find a suitable way so far.
First thing I thought about was to calculate the tan( fA ), which is sin( fA ) / cos( fA ).
But then to get sin( fA ) we'd still need to calculate cos( fA ). So that still leaves 2 'slow' function calls.
The same holds for sin( 2 * fA ) = 2 * sin( fA ) * cos( fA )
Then there's the addition rules...
sin( x + y ) = sin( x ) * cos( y ) + cos( x ) * sin( y )
etc.
Which would only be helpful if fA is a steadily increasing number.

It is correct though that some compilers 'see' that you call cos and sin, and it can optimize it into only one 'slow' call right? Of course we shouldn't rely on this and right now it is a mystery to me as to how the compiler could achieve this in the first place.

L. Spiro wrote:
troublesh00ter wrote:#6:
Code: Select all
ulY = ulIndex / 16UL;            // % is unnecessary if we also need the division
ulX = ulIndex - ulY * 16UL;


I am afraid this is incorrect.


Hmm.. it is correct though that we don't need to get the modulus if we're interested in the result of the division too right?
Only thing I can think of that we need to floor() the ulY
so ulY = floor( ulIndex / 16UL );


On a side note, I think having a thread like this is a really great addition to the forum - gets you thinking deeper about matters that look trivial at first.
troublesh00ter
Sir Hacks-A-Lot
 
Posts: 30
Joined: Mon Jun 01, 2009 2:54 pm
Location: The Netherlands

Re: Quiz

Postby L. Spiro » Sun Dec 06, 2009 9:06 am

x4NG3L wrote:I DONT code in C++ !
I Code in VB
More i Go Try, Only for Fun.


My #2:
Code: Select all
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

struct vVec
{
  float x;
  float y;
  float z;
};


int main ()
{

double fA;
vVec.x = cos(fA);
vVec.y = sin(fA);
vVec.z = sin(fA);
printf ("Is This?");

  return 0;
}


This does not provide the same result as the original snippet. vVec.y is no longer negative.

x4NG3L wrote:My #3:

Code: Select all
#include <iostream>
#include <vector>
using namespace std;


int main ()
{

vector<int> vVector;


int I;
for(I = static_cast<int>(vVector.size() - 1UL); I >= 0; I )
{
  printf ("Is This?" );
}

  return 0;
}


This is at least as problematic as the original snippet.



troublesh00ter wrote:
L. Spiro wrote:
troublesh00ter wrote:#2:
Code: Select all
vVec.x = ::cos( fA );
vVec.y = -::sin( fA );
vVec.z = -vVec.y;          // No need to call sin() twice


Is there something more you can do to this?


I've been trying to come up with ways to calculate cos and sin from one call. But I failed to find a suitable way so far.
First thing I thought about was to calculate the tan( fA ), which is sin( fA ) / cos( fA ).
But then to get sin( fA ) we'd still need to calculate cos( fA ). So that still leaves 2 'slow' function calls.
The same holds for sin( 2 * fA ) = 2 * sin( fA ) * cos( fA )
Then there's the addition rules...
sin( x + y ) = sin( x ) * cos( y ) + cos( x ) * sin( y )
etc.
Which would only be helpful if fA is a steadily increasing number.

It is correct though that some compilers 'see' that you call cos and sin, and it can optimize it into only one 'slow' call right? Of course we shouldn't rely on this and right now it is a mystery to me as to how the compiler could achieve this in the first place.


The fsincos instruction on x86 processors gives you the sine and cosine in one instruction call and is far superior over any alternative way of getting both the sine and cosine at the same time; however, this is not related to the solution for this problem, which must be non-platform-specific.
For the answer, you may assume that the instruction does or does not exist and you may use it or omit it from the 100% answer. Either way, you must still keep searching for that improvement.



troublesh00ter wrote:
L. Spiro wrote:
troublesh00ter wrote:#6:
Code: Select all
ulY = ulIndex / 16UL;            // % is unnecessary if we also need the division
ulX = ulIndex - ulY * 16UL;


I am afraid this is incorrect.


Hmm.. it is correct though that we don't need to get the modulus if we're interested in the result of the division too right?
Only thing I can think of that we need to floor() the ulY
so ulY = floor( ulIndex / 16UL );


On a side note, I think having a thread like this is a really great addition to the forum - gets you thinking deeper about matters that look trivial at first.


It is incorrect to assume we do not need the result of the modulus. In a 16×16 grid, this code walks Y down each column and Y across each row.

Hopefully this quiz will change the way everyone codes; each correct answer is easy to remember and do, and you will definitely use them from now on after seeing them.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby CoMPMStR » Sun Dec 06, 2009 4:30 pm

This may still be incorrect but...

#2:
Code: Select all
float t = ::tan(fA * 0.5f);
float s = (float)(2 * t / (1 + t * t));
float c = (float)((1 - t * t) / (1 + t * t));
vVec.x = c;
vVec.y = -s;
vVec.z = s;


420 Posts!
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby L. Spiro » Sun Dec 06, 2009 4:42 pm

You are looking too deep.
The solution is right in front of you.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby CoMPMStR » Sun Dec 06, 2009 4:50 pm

Then I'd have to say:

Code: Select all
vVec.x = ::cos( fA );
vVec.z = ::sin( fA );
vVec.y = -vVec.z;


So then you don't negate the value twice? ^_^"
:lol: I'm glad wrong answers don't count against you on this quiz.
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby L. Spiro » Sun Dec 06, 2009 10:22 pm

Correct.

There are many ways to speed up sine and cosine calculations, and most of them, including the use of tables, are too involved too post here.
Our goal is not to modify the output at all and this quiz is about the little things you can do in any situation without knowing anything else about the code. Most sine/cosine optimizations trade off precision in favor of speed, and for all we know that precision is crucial to the proper workings of this code (though we can get at least the same or better precision using fsincos on x86, so this would always be a valid enhancement), and there can always be an argument over which is the “best” or fastest optimization to use.

Regardless of the methods of getting the sine and cosine, however, it will always be true that copying to a local and then copying that local will be faster than any sine-generation technique. Thus your rewrite will, in every possible case, be faster than the original source, and it will not modify the result (guaranteeing that you have not broken anything).


troublesh00ter also saw this, but there was just one tiny detail left: No need to do double negation.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby CoMPMStR » Mon Dec 07, 2009 2:50 am

Haha I got one right, w00t!! What's messed up is that I thought of putting the correct answer before the other one, but I figured "let's go see if there's a way to get sin and cos without calling both functions". That's my luck.. :lol:


Here's another submission:

#4: Isn't the ternary operator much faster than calling the std::max function?
Code: Select all
unsigned long ulMax = 0UL;
for ( size_t I = 0UL; I < vVector.size(); ++I ) {
    ulMax = (ulMax <= vVector[I]) ? vVector[I] : ulMax;
}


#5: If we're just toggling an option on or off (0 or 1), instead of doing ulSwitch=!ulSwitch; just do a simple xor by 1. ulSwitch^=1;, I know for a fact that all bitwise operations are faster than anything else and the logical not (!) is NOT a bitwise operation. :D
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby troublesh00ter » Mon Dec 07, 2009 5:09 am

L. Spiro wrote:Correct.
troublesh00ter also saw this, but there was just one tiny detail left: No need to do double negation.


Can't believe I looked over this, seeing twice a '-' should have rang some bells ;). Ah well, here's another go at the modulo/division:

Code: Select all
ulX = ulIndex & (16UL - 1UL);   
ulY = (ulIndex - ulX) / 16UL;


As 16 is a power of 2 we can use a bitwise AND instead of %. Something that I learned from this quiz is that the compiler will put 15 instead of 16 - 1, normally I would write 15UL but I suppose this way the intention is clearer.
A thank you to CoMPMStR (if the answer is correct) for sparking a brain cell with the 'bitwise operation' comment.
troublesh00ter
Sir Hacks-A-Lot
 
Posts: 30
Joined: Mon Jun 01, 2009 2:54 pm
Location: The Netherlands

Next

Return to Knowledge Base

Who is online

Users browsing this forum: No registered users and 0 guests

cron