Any code monkeys in sci?

Can you help me find out what this algorithm does? Any tips for analyzing algorithms in general?

Any code monkeys in sci?

Can you help me find out what this algorithm does? Any tips for analyzing algorithms in general?

7 months ago

It's how European kids learn to multiply without memorizing stupid tables. It's also the same algorithm as repeated squaring.

cpp.sh/6bztc

Enter x: 4

Enter y: 5

x*y = 20

y^x = 625

7 months ago

x and y in parentheses are your inputs. a, b, and c are variables defined when the function is called.

So when you go and use the function like this:

Algoritmo3(5,10)

Then what happens is:

1) a is set to 5

2) b is set to 10

3) c is set to 0

4) While a is still greater than 1

4A) If a is even (which it isn't in our example), then a is set equal to 1/2 of itself and b is set to twice itself.

4B) And if a is not even (which is true of our example) then c is set equal to b plus itself (so 10 for the first iteration of this while loop), a is set equal to 1/2 of itself with the decimal part dropped (so 2 for the first iteration of this while loop), and b is set equal to twice itself (so 20 for the first iteration of this while loop).

So a now equals 2, b now equals 20, and c now equals 10.

2 is still greater than 1, so another iteration ensues.

2 is even, so it goes through 4A instead of 4B this time.

Half of 2 is 1, so a equals 1 now.

Twice 20 is 40, so b equals 40 now.

Another iteration is not performed because a is no longer greater than 1 (it's just equal to it).

So 10 plus 40 equals 50 for c now (the c=b+c line just above the return line).

Finally c is returned, meaning 50 is the output to Algoritmo3(5,10).

Note that I'm not sure why the c=b+c line is counting as outside of the do while loop. I know that's probably what's intended given that this looks like it's meant to take x and y inputs and return the product of those two numbers, but I don't see any reason to consider that last line as existing outside of the do while loop. It definitely exists outside of the if then statement, but if I didn't have the context of apparent multiplication I would have probably interpreted that line as being calculated every time the do while loop iterates.

7 months ago

Wait, I just noticed the extra c=b+c after the if/else block. The result is [math]y(x + 2(2^{\lceil\log_2(x)\rceil+1} -1)) [/math]

But I assume your professor just fucked that up.

7 months ago

He didn't, it's intentionally there. Even one of the questions is related to that specific line there

7 months ago

Was it a trick question then?

Because that line takes a perfectly fine multiplication function and ruins it.

7 months ago

Which roughly translates to "For algorithm3, determine what's the maximum and minimum amount of times that the underlined line will be executed".

But that just begs the question: What's the point of writing all that code if you're just gonna calculate that formula u posted?

I'm sorry but i genuinely feel very stupid right now

7 months ago

Can you help me find out what this algorithm does? Any tips for analyzing algorithms in general?

Write out x in binary. It adds y*2^n to c if x's n-th binary digit is 1, otherwise it doesn't affect c. Then it increases n -> n+1 and adds y*2^n+1 to c. Effectively doing y*x + y*1111...(#of 1s equal to # binary digits in x)....11110_2

7 months ago

For algorithm3, determine what's the maximum and minimum amount of times that the underlined line will be executed

It executes exactly the Hamming weight of x times aka the number of 1's is in x written out in binary.

7 months ago

Sorry if i'm being really stupid here, but what does the output mean then?

With the example above x=5, y=10, the output is 50 and 5 written in binary doesn't have 50 1's

7 months ago

it keep halving x and doubly y while x is even, or settinc c equal to the sum of y and itself, then halving x to return an integer and doubling y again, and then returns c at the end.

You can ignore a=x and b=y since it just makes the manipulation of x and y indirect which is unnecessary.

7 months ago

The output would be 70 and 5 in binary is 101

a=5

b=10

c=0

while(a=5 > 1)

else branch

c=0+10 =10

a=2

b=20

c=10 + 20 = 30

while(a=2 > 1)

if branch

a=1

b=40

c=30 + 40 = 70

while(a=1 > 1)

break

Shit, I keep seeing what I expect to see and not what's there. It actually calculates [math]y(x + 2^{\lceil\log_2(x)\rceil-1} - 2)[/math] since it skips the msb with the while(a>1) instead of while(a>=1)

7 months ago

its obviously an algorithm that multiplies a positive integer x, by some number y

if you want to figure out algorithms like this, it helps to at least have some surface level education in computer science

7 months ago

i just got linked here

real science

Science is gay, of course CS isn't science

7 months ago

101

The underlined c=c+b runs for every 1 in binary not counting the first. So for 5 it runs once.

7 months ago

the underlined line isn't the issue

the bottom-most c = b+c is the retarded line, and it might be a typo because it fucks up a perfectly-fine multiplication algorithm and instead makes it return some retarded shit

the point of analysing code which is equivalent to a math formula is two-fold:

1. it builds your critical thinking skills and allows you to familiarize yourself with how computers work and how computer logic flows

2. even if you have a fancy formula, you don't have a way of automatic computations unless you somehow represent that formula on a computer, and typically if you just write out the formula using the standard library functions it will be much more inefficient than a more "flattened" and complicated-looking algorithm

para de pedirle ayuda al puto Veeky Forums en tu tarea, comepinga

7 months ago

But cs IS math

All my classes involve real proof writing and creating theorems to prove further things . I have not touched a computer and good because I hate technology .

What the fuck is that if not math

7 months ago

the bottom-most c = b+c is the retarded line, and it might be a typo because it fucks up a perfectly-fine multiplication algorithm and instead makes it return some retarded shit

nice autism

it's just triggering you so hard that the function doesn't return the product of x and y isn't it

7 months ago

i'm a different user than the other guy

the OP is frustrated because he doesn't understand why he's asked to analyse the program

i'm explaining that the program doesn't do anything special, but if one simple modification is made it would

how does it feel being clinically autistic, user?

7 months ago

desu i know next nothing about coding and determined what it was just by reading the statements literally

7 months ago

Imagine being so retarded you conflate true applied mathematics and the non sense that gets taught in your local CCs "business math" course.

7 months ago

Imagine being so retarded you conflate true applied mathematics and the non sense that gets taught in your "computer science" course.

7 months ago

when a is odd, a=(2floor(a/2)+1), so the underlined c=b+c is for counting the term 1*b in a*b.

7 months ago

This website may contain content of an adult nature. If you are under the age of 18, if such content offends you or if it is illegal to view such content in your community, please EXIT.

Enter Exit

We use cookies to personalize content and ads, to provide social media features and to analyze our traffic. We also share information about your use of our site with our advertising and analytics partners.

Accept Exit