-3

Is there a way to implement the log function witch works for string numbers without converting the string to a int? example of string number: char *stringNumber = "432" the string represents only integers(whole Numbers) but they can be near infinitely long the log should return an int as well(represented as a string) if i result is a float the decimal part should be removed (no rounding)

i know that for numbers you can implement:

int logn(int n, int x)
//n is the number , x is the base
{
    if (n <= r-1)return 0;
    return (1 + logn(n/x, x);
}

but for a string i have no idea how to do it

El45n
  • 1
  • 4
  • 2
    Is there a reason you *don't* want to convert the string to a number first? – dbush Mar 22 '22 at 20:29
  • Elian Dochev, Do you want to find the _binary_ log for a string with _decimal_ digits? Or find the _base_ log for a string with the _same_ base digits? The first is hard, the 2nd is easy. – chux - Reinstate Monica Mar 22 '22 at 20:31
  • What is a "string number"? I would suggest to clearly specify the term, and provide some relevant examples (in particular, addressing range and precision). – njuffa Mar 22 '22 at 20:33
  • Use [`strtod()`](https://pubs.opengroup.org/onlinepubs/9699919799/functions/strtod.html) to convert the string to a `double` (or `strtol()` to convert to an integer). – pmg Mar 22 '22 at 20:34
  • @ElainDochev Would all string numbers be integers, as the example suggests? What would the desired output look like? – njuffa Mar 22 '22 at 20:39
  • @njuffa string number is string that contains only chars that are digits(char > = '0' && char <= '9') – El45n Mar 22 '22 at 20:42
  • @chux preferably if it can do any base logn(X) – El45n Mar 22 '22 at 20:45
  • 1
    @ElianDochev Is there a limit to the number of digits? What would the output of the envisioned log function look like? An integer? A fixed-point number? A floating-point number? A string (what kind, given that logarithm generally produces results with a fractional component)? What base should the logarithm use? Base 10, base 2, base e, something else? – njuffa Mar 22 '22 at 20:47
  • 1
    Edit the post to contain the information solicited by comments. Do not just answer in comments. – Eric Postpischil Mar 22 '22 at 20:47
  • @dbush yes because it should be able to go to infinite aka without overflow and im not allowed to use libraries (for example cant use int64_t) – El45n Mar 22 '22 at 20:48
  • Elian Dochev, that broadens the goal. It is already unclear. – chux - Reinstate Monica Mar 22 '22 at 20:48
  • 1
    @ElianDochev "not allowed to use libraries (for example cant use int64_t)" is unclear. `int64_t` is only a type. There is no library of functions associated with it. – chux - Reinstate Monica Mar 22 '22 at 20:50
  • The base-two logarithms of many numbers are irrational. What do you want returned for, for example, log2(3)? Just the integer part, 1? Some number like 1.584? In a `double`, in a string using decimal, something else? How many digits should it provide? How accurate does it need to be? – Eric Postpischil Mar 22 '22 at 20:50
  • @njuffa i should probably mention that the string will only be dealing with integers but they can be infinitely long , the log should return an int (represented as a string) as well – El45n Mar 22 '22 at 20:52
  • 1
    Are you using “int” to mean the actual C type `int` or as an abbreviation for “integer”? If the logarithm is 1.6, should the routine return 1 (truncated) or 2 (rounded) or something else? – Eric Postpischil Mar 22 '22 at 20:54
  • 1
    If the integers can be "infinitely long", then the process of finding the logarithm, regardless of the method, will also be infinitely long. Perhaps you meant "arbitrarily long"? – SGeorgiades Mar 22 '22 at 20:58
  • @EricPostpischil just as a whole number not the int data type – El45n Mar 22 '22 at 20:59
  • 1
    @SGeorgiades by infinitely long i mean very very big – El45n Mar 22 '22 at 21:00
  • Your sample code doesn't use `x` at all. What base is the number string in, and what is the base of the log? If they're the same, the answer is trivial. – dbush Mar 22 '22 at 21:03
  • `int` (or `long long int` or `int256_t` when it is available) is not wide enough for "very very big" numbers. You need to **devise your own data structure and write your own functions** (sum, subtract, multiply, division, exponentiation, root, logarithms, ...) or use a library. – pmg Mar 22 '22 at 21:06
  • 2
    To answer the literal question in the post, “Is there a way to implement the log function”: Yes, you can perform long division, dividing the input number by the base and discarding the remainder. Doing this repeatedly and counting the repetitions produces the logarithm (the number of repetitions until the quotient is less than one is the greatest integer not greater than the logarithm). Techniques for long division taught in elementary school will work. They may be slow for large inputs. – Eric Postpischil Mar 22 '22 at 21:09
  • There is no way to combine the logarithms of individual digits, you have to work with the whole number. That's going to require a library. – Mark Ransom Mar 22 '22 at 21:12
  • 1
    @EricPostpischil thx that's what i was looking for – El45n Mar 22 '22 at 21:13
  • you have to implement math operations on strings, for integers only its relatively easy: `a^x=b; x=log_a(b);` so just increment x until it `a^x` matches b ... so do a simple for loop like: `for (x=0,bb=1;bb<=b;bb*=a,x++);` so no recursion (which is not a good idea for strings) and only `+1,*` operations on strings you can use long multiplicaiton like you would compute it on paper... – Spektre Mar 23 '22 at 07:42
  • implementing addition is simple ... in case you got really huge numbers you can have to use better multiplication like Karatsuba, or even NTT based like this one [`char* mul_NTT(const char *sx,const char *sy)`](https://stackoverflow.com/q/18577076/2521214) but that one is for really HUUUUGGEEEE numbers. The `log` itself might be speed up by binary search ... Your current approach is a BAD IDEA because you have division inside and recursion with string in tail that is just asking for Stack overflow, memory leaks and implementing and dealing with division is much harder than multiplicaiton. – Spektre Mar 23 '22 at 07:54

3 Answers3

0

You need to convert the string to a number

 char * numStr = "2.7";
 double num = strtod(numStr, NULL);
pm100
  • 48,078
  • 23
  • 82
  • 145
  • int str_to_int (char *scr) { int number = 0; int i = 0; while (scr[i]) { number = number * 10 + (scr[i] - '0'); ++i; } return number; } – El45n Mar 22 '22 at 21:03
  • @ElianDochev ok, that converts a string to an intgere too, so whats the question – pm100 Mar 22 '22 at 21:05
  • @ElianDochev You said "without converting the string to a int"; perhaps you meant "without converting the string to an int with a library function? – SGeorgiades Mar 22 '22 at 21:17
  • yeah that is correct but for that you still need your own datatype to store the potentially near infinite number – El45n Mar 22 '22 at 21:19
  • @ElianDochev OK now you asking a very different question , "how can I do math on a number like this - '7854389076547896543890976543'". For that you need a Big Integer library - google it – pm100 Mar 22 '22 at 21:30
0

thanks to @EricPostpischil for the answer perform long division, dividing the input number by the base and discarding the remainder. Doing this repeatedly and counting the repetitions produces the logarithm (the number of repetitions until the quotient is less than one is the greatest integer not greater than the logarithm; the answer of @pmg is also a good way to do it i thinks

El45n
  • 1
  • 4
-1

Even your example function has typos in it. It appears you meant for it to return the integer part of the logarithm base x of n, with a floor function applied to the result. To accomplish this it would have to be:

int logn(int n, int x)           // n is the number, x is the base
{
    if (n <= x - 1) return 0;    // note: x, not r
    return (1 + logn(n / x, x);  // note: x, not 2 for the division
}

All that being said, I don't see any way of taking an arbitrary-base logarithm of a stringified number without converting it to a numeric value first. If you wanted only a base-10 logarithm, it would be possible.

SGeorgiades
  • 1,771
  • 1
  • 11
  • 11