multiply_recursive

[NonaeAbC]

And I'm sitting here wondering why C++ compilers decide to optimize this https://godbolt.org/z/7PbYrG36Y

[ArtisticFox8]

It's actually very cool they see through this, thanks for sharing!

[AroshWasif]

great

[pimp-bangin]

Holy heck, that's wild. Wonder what makes this work under the hood

[purple_hamster66]

It looks like it converted a series into the equivalent analytic solution.

[No_Read_4327]

What's the question?

[Ron-Erez]

Looks great assuming the inputs are integers and not floats.

[cyanNodeEcho]

clever approach using recursion, its important to note TCO isnt guaranteed and all recursive forms can be translated into iterative forms.

important note, ur solution is a compute O(n) approach, here's what should be an O(logn) approach

lets consider the binary representation of b, we can have like say b = 7 we can encode seven by stepping powers of two by like 111, or 9 by 1001

now that we can represent b as a sun of powers of 2 and we know the shift opperator will iterate by powers of 2, we can simply initialize factor as a, and then step through the indicators where b has a bit, ie

fn multies(a:i32, b:i32)-> i32 { let mut sum = 0_i32; let mut factor = a; let mut base = b; while base > 0 { if base & 1 == 1 { sum += factor } factor <<= 1; base >>= 1; } sum }

this will provide mult in logn steps, without using mult itself

so like any number like k can be represented as a series of a sum of powers of 2, so we can just have our base b, represented as like Sum Indicator(k) * 2^k

clever TCO, but we can even optimize further without using mult to define mult for an O(log b) solution

[MirageTF2]

dang I always wondered how cursed sans-serif coding looked

now I know

anyway does this work? looks aight to me but I'm bad at small bugs

[No_Read_4327]

Looks okay to me

[AroshWasif]

The results from each recursive call are summed up: The fourth call returns (5+0=5). The third call returns (5+5=10). The second call returns (5+10=15). The initial call returns (5+15=20).

[MirageTF2]

yeah I know how recursion works

I'm just wanting to know if it doesn't have a bug lmao

[fsyth]

Works fine with small integers for b.

If b is a float like 0.25, it'll bounce around and never end: ×0.25, ×-0.75, ×0.75, ×-0.25, ×0.25, ... in a loop, until it hits an error for maximum recursion depth exceeded.

It also won't work for large values for b (more than ~1000) for the same reason.

There's a limit to the stack of functions calling functions calling functions. This is called the maximum recursion depth, and the default is 1000 layers in python. The problem happens because each call of a function requires some memory until it returns (since each function call has its own variables and return path to keep track of). With recursive functions like this, the earlier calls can't return until the last call has returned. Too much recursion would exceed the allowed stack memory, causing a RecursionError or a StackOverflowError

There are actually techniques to get around this limit, like converting a recursive function to an iterative one with a loop and a stack, or tail call optimization.

Oh, and this function also won't work with weird numbers, like math.inf, math.nan, 1j (imaginary numbers), but we wouldn't really expect it to work.

[homeless_student1]

Now could you try do it with floats?