Programming challenge:
write a good function/method/subroutine for calculating exponents, such that f(a,b) = aᵇ
choose whatever language you want
#include <math.h>
double exp(double a, double b) {
return pow(a,b);
}
F (a,b):
Int result = 1
For int I = 0, I < b, i++:
result *= a
Return result
>>53754344
>exp
>not already defined in math.h
good joke lmao
>>53754383
>O(n)
Nice try. I said a good function, not an easy one
>>53754269
are a and b integers? can b be negative?
wouldn't you use square and multiply for positive integers?
Should b be IEEE floating point, or an integer? If the former, best to just use the standard library, because it may very well alias a hardware specific instruction. Otherwise, I've got a homebrew square and multiply algorithm floating around.
>>53754269
Don't feel like writing it because on phone, but make methods that do exponents of all numbers.
Function two returns a*a
Function seven returns a*a*a*a*a*a*a
Etc.
Have a switch that has cases for every number. Call corresponding function for number.
Voila, you have an O(1) method.
power :: Integer -> Integer -> Integer
power n k | k < 0 = error "power: negative argument"
power n 0 = 1
power n k = n * power n (k-1)
power1 :: Integer -> Integer -> Integer
power1 n k
| k < 0 = error "power1: negative argument"
power1 n k = product (replicate (fromIntegral k) n)
power2 :: Integer -> Integer -> Integer
power2 n k
| k < 0 = error "power2: negative argument"
| k == 0 = 1
| even k = power2 (n*n) (k `div` 2)
| otherwise = n * power2 n (k-1)
python:
def exponent(a, b):
return a**b
>>53756555
>switch with cases for every number
nigga what? enjoy your infinitely large switch block.
>>53756851
I mean you could use metaprogramming to do it.
But it's still a stupid idea.
>>53756889
If you did that it would no longer be O(1) which defeats the point entirely.
>>53756923
Not if you just generate the source once, no need to do it every time.
>>53754269
For integer powers I'd use the binary method, like, x^9=((x^2)^2)^2*x, it's O(log(N))
Not sure about fractionals, maybe turn decimal fraction into simple fraction, then reduce?
Negatives are just 1/x;
Don't care enough about that now, I did similar shit for Fibonacci numbers once(using n+1 and 2n formulas).
>>53757072
Alright I actually did it.
http://pastebin.com/zQWxfVwc
That will generate a header pow.hpp with a switch statement for values b in [1, n] where n is the argument you gave.
package com.company.util.math.exponent;
public class ExponentiationBuilderFactory {
public static EmptyExponentiationBuilder builder() {
return new EmptyExponentiationBuilder();
}
public static final class EmptyExponentiationBuilder {
private EmptyExponentiationBuilder() {}
public BaseExponentiationBuilder setBase(double base) {
return new BaseExponentiationBuilder(base);
}
}
public static final class BaseExponentiationBuilder {
final double base;
private BaseExponentiationBuilder(double base) {
this.base = base;
}
public FullExponentiationBuilder setExponent(double exponent) {
return new FullExponentiationBuilder(base, exponent);
}
}
public static final class FullExponentiationBuilder {
final double base;
final double exponent;
private FullExponentiationBuilder(double base, double exponent) {
this.base = base;
this.exponent = exponent;
}
public double calculate() {
return Math.pow(base, exponent);
}
}
}
>Programming challenge:
>do my homework
package com.company.util.math.exponent;
class ExponentiationCalculator {
private final long base;
private final long exponent;
ExponentiationCalculator(long base, long exponent) {
this.base = base;
this.exponent = exponent;
}
long calculate() {
return calculate(1, base, exponent);
}
private long calculate(long x, long b, long e) {
if(e == 0) return x;
if(e % 2 == 0) return calculate(x, b*b, e/2);
return calculate(x*b, b, e-1);
}
}
What's a stack overflow?
>>53756555
>switch
>O(1)
No, sorry.
>>53754269
Might as well asked to do it in assembly
>>53754269
im not doing your homework, faggot
>>53754383
>only works for integer powers
top kek