You are here

Another puzzle, another prize! | Cypress Semiconductor

Another puzzle, another prize!

It has been some time since I have given something away.  So I think it is time for another contest.  This time you are competing for a PSoC 5 DEV KIT  (-050). First to answer correctly wins!

 The function y = f(x) where both x and y are integers and x is a non negative value.

 The function is implemented with the following code;

 Given a non negative integer x:

 

    for(y = 0; x > 2*y; x -= 2*y++);

 

1) What is this function?

2) Prove it works for all non negative values of x.

3) What is the answer for a negative value of x?

Comments

acemax's picture

Hi Dave,

Not sure if I'm right, but let's try!

1) What is this function?
A: It is an inverter.
Ex: input = 50
output = -50

2) Prove it works for all non negative values of x.

A: Using matlab.
clc
clear all
close all

%input
y=0;
temp = 0;

hold on
for x=1:50
if (x > (2*y))
x = (2*y)-x;
temp = temp+1;
end
stem(temp,x);
end

result graph demonstrates all input values of x inverted.

3) What is the answer for a negative value of x?

A: Assuming that test condition is x>2*y; y=0, the statement will be skiped, so input value will be unchanged.

Best regards,
Andre Fernandes
Brazil

hli's picture

You always ask such questions on a friday evening when I'm away for the whole weekend. But I cannot leave them unanswered :)

1) it calculates y=round(sqrt(x))

2)
My math is a little bit rusty, so I don't have a real, mathematical proof. But
I can explain how it works:

* the definition of y=floor(sqrt(x)) is the number y, where y**2<=x<(y+1)**2 (but this is _not_ what is calculated here)

* n**2 can be calculated as the sum of the first n _odd_ integers

* the code above calculates the sum of the first y _even_ integers (this is the 2*y++ part)

* the sum of the first n even integers lies always just 0.5 below the
middle of the first n odd integers and the sum of the first n+1 odd integers

* the code stops, when this sum is close enough to x (this is the x>2*y part)

* this criteria is true when the next addition to the sum of even integers
would go above x

* so for calculating floor(sqrt(x)), we would just add the first y odd integers,
(which gives us the y-th square number) and stop when we reach
(or overflow) x, with y as the result

* but since we add even integers, the sum is always halfways between two square
numbers, so we increase y sooner - which effects in rounding up the square root

* we can never hit, with our calculation a number 'n.5', because 'n.5'**2 ends up
in the form 'm.25'

3) for negative numbers, it just returns 0 (since x is always smaller than 2*y),
and this is OK since the square root of negative numbers is not defined for
rational / real numbers

Arther's picture

1) This function finds the integer square root of x with rounding.
2)the simplification of above function will like as below
x(n)=x(n-1) - 2*n for x(n)>2n
so Convergence of this function will be Y;
Z transform of above series will be -2/(1-z^(-1)) So for non negative number ROC will be always |z|<1 so it will converges at some finite value.

3) For negative value of x the answer y will hold 0 according to "for" loop.

Arther's picture

rftgrf

GIL's picture

Hi,
integer = 16bit? 32 bit?
1) Y = 50 * SQRT(1 - [(X +(2550 - Xi))/2550]) where Xi is the first value of X (value given)
2) Not possible to work with negative values because you have a strict condition. For Xi=-32768, Y=0 and next value for X will be 2 (thinking in 16 bit, with sign) but with you strict condition, result is false so, not possible to continue. Other thing is the response of the curve
3) Curve is displaced to left.
Meaning of this function? I don't know (by now ;-) ).

acemax's picture

Hi Dave,

I have another try:

1) Its an inverter, the statement is executed just once cause for x>0 the output always will be -x;

2) As the Y will be always zero, we have the follow condition:
X>2Y -> X>0 (condition);
Now, let's call the output value as A, so if Y=0, we have:
A=(2Y)-X -> A=-X;
Finally for X>0 -> A=-X;

3) If the input value (X) is negative it does not meet the condition (X>0), in other words, will just skip the statement and X will be unchanged.

Thank you,

Andre P. Fernandes

Melik Sah's picture

1) C-Code is implemented for x=-y(y+1) + Xi, where Xi is the initial value of x (or Xi is the value of x, when y=0)

2) 2y is subtracted from x, if and only if x>2y, therefore x is always positive. Otherwise for-loop will terminate.

3) for a negative value of x, for-loop will not execute, because x>2y condition will not satisfied for positive values of y, and after for-loop x=Xi, and y=0.

ALL CONTENT AND MATERIALS ON THIS SITE ARE PROVIDED "AS IS". CYPRESS SEMICONDUCTOR AND ITS RESPECTIVE SUPPLIERS MAKE NO REPRESENTATIONS ABOUT THE SUITABILITY OF THESE MATERIALS FOR ANY PURPOSE AND DISCLAIM ALL WARRANTIES AND CONDITIONS WITH REGARD TO THESE MATERIALS, INCLUDING BUT NOT LIMITED TO, ALL IMPLIED WARRANTIES AND CONDITIONS OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT OF ANY THIRD PARTY INTELLECTUAL PROPERTY RIGHT. NO LICENSE, EITHER EXPRESS OR IMPLIED, BY ESTOPPEL OR OTHERWISE, IS GRANTED BY CYPRESS SEMICONDUCTOR. USE OF THE INFORMATION ON THIS SITE MAY REQUIRE A LICENSE FROM A THIRD PARTY, OR A LICENSE FROM CYPRESS SEMICONDUCTOR.

Content on this site may contain or be subject to specific guidelines or limitations on use. All postings and use of the content on this site are subject to the Terms and Conditions of the site; third parties using this content agree to abide by any limitations or guidelines and to comply with the Terms and Conditions of this site. Cypress Semiconductor and its suppliers reserve the right to make corrections, deletions, modifications, enhancements, improvements and other changes to the content and materials, its products, programs and services at any time or to move or discontinue any content, products, programs, or services without notice.