Any code monkeys in sci?

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

Adrian Wright

Any code monkeys in sci?

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

Joshua Russell

Literally 2nd grade textbook multiplication retard.

Robert Brown

?

Camden Bailey

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

Brody Jackson

...

Juan Williams

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.

Oliver Morales

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.

Aiden Ortiz

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

Lincoln Moore

Was it a trick question then?

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

Hudson Torres

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

Andrew Collins

>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

Jace Thompson

>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.

Christian Hill

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

Alexander Wright

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.

Robert Brooks

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)

William Reed

max floor(log_2(x))

min 0

Bentley Richardson

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

Julian Wood

i just got linked here

>real science

Science is gay, of course CS isn't science

Xavier Young

and 70 and 101 are related why...?

Alexander Wright

>101

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

Levi King

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

Joshua Sanders

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

Julian Fisher

>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

Bentley King

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?

Henry Sullivan

That's like saying Business is math because they do "business math".

Mason White

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

Caleb Cruz

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

Levi Sullivan

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

Landon Hill

I've seen this called Ethiopian Multiplication.

Julian Williams

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.