Any code monkeys in sci?

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

LuckyDusty

Any code monkeys in sci?

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

16 months ago

FastChef

Literally 2nd grade textbook multiplication retard.

16 months ago

Nojokur

?

16 months ago

Fried_Sushi

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

16 months ago

Garbage Can Lid

/g/

16 months ago

viagrandad

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.

16 months ago

happy_sad

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.

16 months ago

takes2long

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

16 months ago

iluvmen

Was it a trick question then?

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

16 months ago

Poker_Star

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

16 months ago

Snarelure

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

16 months ago

Firespawn

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.

16 months ago

Dreamworx

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

16 months ago

Boy_vs_Girl

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.

16 months ago

lostmypassword

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)

16 months ago

Techpill

max floor(log_2(x))

min 0

16 months ago

Methshot

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

16 months ago

PackManBrainlure

i just got linked here

real science

Science is gay, of course CS isn't science

16 months ago

Skullbone

and 70 and 101 are related why...?

16 months ago

Evilember

101

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

16 months ago

SniperGod

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

16 months ago

hairygrape

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

16 months ago

iluvmen

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

16 months ago

w8t4u

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?

16 months ago

hairygrape

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

16 months ago

Skullbone

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

16 months ago

TalkBomber

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

16 months ago

Dreamworx

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

16 months ago

Soft_member

I've seen this called Ethiopian Multiplication.

16 months ago

Techpill

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.

16 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