2

This question I have didn't fully help me, although it gave me a few details.

My current based code:

#define e 2.7182818284590452353602874713527

double logarithm(long double dec) {
    // return log10f(dec);
    return result;
}

What I learned from the linked question:

  1. Logarithmic functions use e as base. Stated by the accepted answer.
  2. Also by the accepted answer, ^ is not for exponents (and I'm planning on making this syntax an exponential form, which might mean abandoning the power() function), rather it's an XOR operator.
  3. Someone answered my question but got deleted. It is about the log10f source code, but it's kinda confusing, so not worth it for me.

Now the criteria I have for this function is that it is made from scratch, no multiple functions, and make it a simple sort (even though I doubt that logarithm isn't even simple).

The answer's code:

#include <math.h>

float log_num(int num) {
    return log10f(num);
}

Yes, fairly simple, but as a challenge, I want to not use the log() functions themselves though I'm still relying on <math.h>'s functions.

Question: What's a simple form of making a logarithm function in scratch without the built-in logarithm functions? If without using <math.h>, then how is that?

Stef
  • 13,242
  • 2
  • 17
  • 28
BMPL
  • 35
  • 16
  • This is a math question, not a programming one. You want to know how to calculate a logarithm without a calculator. – user253751 Nov 18 '20 at 14:03
  • 1
    @user253751 For starters, it is both. Asking this in [Mathematics Stack Exchange](https://math.stackexchange.com) won't do anything. Not even Code review will help. – BMPL Nov 18 '20 at 14:18
  • What did Mathematics Stack Exchange tell you about how to calculate a logarithm? – user253751 Nov 18 '20 at 14:34

3 Answers3

2

First remark: All logarithms are proportional. That means if you have a function that computes the binary logarithm, you can use it to deduce the decimal logarithm or the natural (base e) logarithm. In particular, log10(x) = log2(x) / log2(10).

Second remark: For a number n, ceil(log10(n+1)) is the number of digits of n when n is written in decimal notation. Similarly, ceil(log2(n+1)) is the number of bits of n when n is written in binary. Numbers in computers are represented in binary, so getting the number of bits shouldn't be too hard. This gives us the approximation log2(n) ≃ nbbits(n) - 1 for an integer n >= 1.

Third remark: Counting the bits works for an integer. We can extend to a double greater than 1 by rounding it to int. For a double x between 0 and 1, we can use the formula log(x) = -log(1/x) and apply our approximation to 1/x.

#define log_10_of_2 (0.30102999566)
#define log_e_of_2 (0.69314718056)

unsigned int nbbits(unsigned int n)
{
    unsigned int count_bits = 0;
    while (n != 0)
    {
        n = n >> 1;
        ++count_bits;
    }
    return count_bits;
}

double approx_decimal_log(double x)    /* assume x > 0 */
{
    if (x < 1)
        return -approx_decimal_log(1/x);
    return (nbbits((unsigned int) x) - 1.0) * log_10_of_2;
}

This approximation has a precision of about 0.3.

This comes from the fact that nbbits is within 1 of the binary logarithm, and we multiply by 0.3 to get the decimal logarithm.

Stef
  • 13,242
  • 2
  • 17
  • 28
2

If you need something reasonably accurate, you could use the Taylor series formula. Increase the number of iterations if you need better precision.

#define EULER_CONST 2.718281828459045235
#define TAYLOR_ITERATIONS 20

double nat_log(double x) {
    // Trap illegal values
    if (x <= 0) {
        return 0.0/0.0;  // NaN
    }
    
    // Confine x to a sensible range
    int power_adjust = 0;
    while (x > 1.0) {
        x /= EULER_CONST;
        power_adjust++;
    }
    while (x < .25) {
        x *= EULER_CONST;
        power_adjust--;
    }
    
    // Now use the Taylor series to calculate the logarithm
    x -= 1.0;
    double t = 0.0, s = 1.0, z = x;
    for (int k=1; k<=TAYLOR_ITERATIONS; k++) {
        t += z * s / k;
        z *= x;
        s = -s;
    }
    
    // Combine the result with the power_adjust value and return
    return t + power_adjust;
}
r3mainer
  • 23,981
  • 3
  • 51
  • 88
  • 2
    Just a micro-optimization: you can start the Taylor iterations with `t= z= x` and drop the variable `s` using `z*= -x`. –  Nov 18 '20 at 17:21
  • Proud of this answer. I modified it to not just use *e*, but a new `int`/`double` should be used to be added as the base. – BMPL Nov 19 '20 at 13:49
1

While certainly not the best, I think a very simple approach would be to make a function that performs a binary search through all possible answers until it finds the correct one.

pseudo-code

#define e 2.7182818284590452353602874713527

double logarithm(long double dec) {
  double answer = <<half of max>>;
  double step = <<quarter of max>>;
  while(!done) {
    if (exponent(e,answer) == dec) {return answer};
    else if (exponent(e,answer) > dec) { answer -= step;}
    else if (exponent(e,answer) < dec) { answer += step;}
    step /= 2;
  }
}

I would like to emphasize that this is not efficient, has not been tested, and might make your computer self-destruct.

Jacob Geigle
  • 60
  • 4