Win a copy of Transfer Learning for Natural Language Processing (MEAP) this week in the Artificial Intelligence and Machine Learning forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Tim Cooke
• Paul Clapham
• Devaka Cooray
• Bear Bibeault
Sheriffs:
• Junilu Lacar
• Knute Snortum
• Liutauras Vilda
Saloon Keepers:
• Ron McLeod
• Stephan van Hulst
• Tim Moores
• Tim Holloway
• Piet Souris
Bartenders:
• salvin francis
• Carey Brown
• Frits Walraven

# For any integer, n, predict the binary string length, x

Greenhorn
Posts: 27
1
WAIT, not so fast there you cattle rustlers!!! There's a caveat: no iterations, no looping, no recursion, no tables, no lists, nor any such devices which renders the problem absurdly simple. Also, this would for "pure" integers not the java primitive, so for java we would need to include any BigInteger if that makes any difference.

I've been attempting to solve this, but a mathematician I amn't. At first glance, it looked so simple, but I started working on it and everything I have tried has failed.

It's apparent to me--yet may seem foolish to you--the best way to start is to find the mathematical expression that solves the following sequence:

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023...

You can establish this pattern by starting with 1 (n0) and taking the binary sequence element at n+1 and summing them together. The first element of this sequence is 1. The second element is 3 (first element of this sequence plus second element of the binary sequence, which is two). The third element is 7 (the second element of this sequence, three, plus the third element of the binary sequence, four) on into infinity.

So the expression needs to work something like this:

any number less than 2 and greater than or equal to 0 will return 1 and...
any number less than 4 and greater than or equal to 2 will return 2 and...
any number less than 8 and greater than or equal to 4 will return 3 and...
so on and so forth.

The solution would be a Java expression that could produce the following examples:

input: 7
output: 3

input: 100
output: 7

input: 32498531901
output: 36

If there's any math persons out there cringing at my naive attempts to explain and constrain the problem. You have my apologies. Also, if the underlying class utilizes any recursive or iterative techniques that's ok, like I'm sure many of the java.lang.Math functions use iterations of some sort, but that's fine. There just can't be anything like that in the solution expression.

David Gillette
Greenhorn
Posts: 27
1
Example of absurdly simple: lang.Integer.toBinaryString().length() - nothing like that.

It should be like (math.sqrt(some*crazy)/expression-that+I(won't/ever))+figure/Math.pow(out*but, might);

Marshal
Posts: 25433
65
• 1
From the math-guy point of view x is the integer greater than or equal to log ₂(n), except when n is 0 or 1 then x is 1.

Saloon Keeper
Posts: 11877
253
• 1
Yup, I'm with Paul.

Every additional binary digit (bit) doubles the range of integers that can be represented. The formula for determining the largest integer x that can be represented with n bits is 2ⁿ-1. Solving for n gives n = ⌈logâ‚‚(x+1)⌉

David Gillette
Greenhorn
Posts: 27
1
Wow, that is simple, ugh, very humbling.

So you guys are saying the expression is something like

x = (n > 1) ? ((int) log2(n)) + 1 : 1;

But java has no log base 2 math function, or does it?

David Gillette
Greenhorn
Posts: 27
1
Ok, I just used this thing called the internet to find the change-of-base formula.

The expression would be:

int x = (n > 1) ? ( (int) log10(n) / log10(2) ) + 1 : 1;

That did it! Thanks smart dudes! [hat-tip]

David Gillette
Greenhorn
Posts: 27
1
The "guts" of a logarithm is a series. Please don't freak out about this oxymoronic question I'm about to ask: Is there a way to calculate a series without iterative work? Is there a math that can do this? At the bare metal level?

Paul Clapham
Marshal
Posts: 25433
65
I don't understand what you mean by "calculate a series".

On the face of it, "iterative work" seems to mean "doing something repeatedly". And if you want to evaluate each term of a series, then it seems likely that you would have to repeatedly evaluate each term.

On the other hand if you wanted to calculate the sum of a series, then it isn't necessarily true that you have to evaluate each term and sum them up. Sometimes there are other ways -- see for example the legend about how Gauss summed the numbers from 1 to 100 when he was a child.

David Gillette
Greenhorn
Posts: 27
1
Fascinating.

Paul Clapham
Marshal
Posts: 25433
65

David Gillette wrote:The "guts" of a logarithm is a series.

I wouldn't say that. The logarithm of a number X is simply another number Y for which 10^Y, or 2^Y, or e^Y = X. (Depending on the base of the logarithm.)

Now it's certainly possible to write a Taylor series whose sum converges to the function log(x), but that doesn't mean that log(x) "is" that series.

Likewise it's possible that software which computes log(x) uses some kind of series to determine that value (or at least a good approximation to it), but that doesn't mean that log(x) "is" that series either.

Stephan van Hulst
Saloon Keeper
Posts: 11877
253

David Gillette
Greenhorn
Posts: 27
1
I don't know the parlance of the mathies. I'm not making any technical sense. I'm just a simple greenhorn, but I'm trying communicate this thing and I do appreciate your patience while I blunder through it.

I don't want to get caught up in trivialities such as what exactly log(x) "is", as far as java is concerned it is nothing more than a static method in the math class. The question I was attempting to ask is about the type of calculation process that is involved in solving a logarithm. Plus when you use ""is"" all I can think about is this: https://youtu.be/BS-cip2brsg?t=14

From what I understand (and that isn't much), the calculation of a logarithm requires some type of iterative work. You directed me toward Gauss and his unique way to calculate the sum of the series of the first 100 integers. That was very interesting. It makes me think that there might be a way to calculate a logarithm in a manner that doesn't involve iterative work. Do you know if this is possible? Is there some truth statement that says something like, "the sum of any series or iterative calculation process can also be solved through an algebraic generalized form which does not utilize any type of iterative process"?

Paul Clapham
Marshal
Posts: 25433
65
Well, first of all you do realize that those calculations in the java.math classes don't actually calculate the logarithms of the numbers they are given? They compute a very good (from the human point of view) approximation to the logarithms, but they can't compute the exact values because almost all logarithms are irrational and Java's double values can only represent rational numbers.

There is no possible calculation which can return the decimal expansion of log(3) because it would take forever to compute the infinite number of unpredictable decimal places.

However mathematicians care nothing for that because it's perfectly possible to do arithmetic with log(3). For example 2 * log(3) = log(9). As long as you don't care about displaying decimal values, it's all fine.

As for what kind of calculations are used in the real world to calculate the approximate value of a logarithm, I would expect that there's some kind of Taylor series (or similar) which is evaluated one step at a time until the steps are too small to make a difference. And no doubt there's a whole lot of optimization involved which makes the actual calculations run a lot faster then the naive version which I just described.

lowercase baba
Posts: 12827
52

Paul Clapham wrote: the infinite number of unpredictable decimal places.

I think the very fact that you CAN calculate it means it is ABSOLUTELY predictable.  ;-)

Stephan van Hulst
Saloon Keeper
Posts: 11877
253
Logarithms are not algebraic, and therefore you need iteration to approximate their solutions. While some series can be calculated using a simple algebraic formula, other series can not.

Marshal
Posts: 68862
275
But irrational numbers are inherently unpredictable. You cannot tell what follows next if you get a sequence 345, and when you have π to 31415926535897 digits, you can pretty well rely on “345” occurring several imes.

fred rosenberger
lowercase baba
Posts: 12827
52
I think we have a different definition of "predictable" and "unpredictable".

To me, unpredictable means that regardless of what information you have, it is IMPOSSIBLE to accurately name the next thing.  No matter how many times I spin a roulette wheel, I can only name the next number correctly 1 out of 37 or 38 times (depending on the wheel type)

Pi, sqrt(2), log(47)...whatever....for all of these, if i have the right information, I can with certainty tell you what the next number will be.

Stephan van Hulst
Saloon Keeper
Posts: 11877
253
You mean, given a subsequence of the decimal representation of an unknown irrational number, you can't predict what sequence will follow it. If I know what irrational number is being represented, I can predict it given enough computational power.

The same is true for rational numbers by the way. If I have the subsequence 0.333333333333 and I don't know of what rational number it is a subsequence, I will not be able to predict what comes next.

This was a reply to Campbell.

Campbell Ritchie
Marshal
Posts: 68862
275
Rational numbers can be expressed in the format numerator ÷ denominator and cannot have a unique sequence of digits longer than denominator − 1 digits. If 0.3333333333333... represents ⅓, that has a unique sequence one digit long (3). You can predict that it is followed by 3, just as you can predict that “28” is followed by “5714” in the recurring part when the numerator is 7, 14, 18, 35 or many other multiples of 7. If you try ¼, that has a two‑digit unique sequence (25) which only occurs once because it can be expressed exactly in decimal numbers.
But irrational numbers aren't like that. Without knowing how far from the decimal point you have gone, you cannot tell which instance of “345” you have, nor what follows it. If you have the expansion of the number, you can find the first occurrence of “345” and find out the following digit, but that is not what I would call predictable. An occurrence of “345” chosen haphazrdly is not followed by a predictable subsequence. Although you can surmise that “345” will occur about once every 1,000 digits, you cannot predict how often it will occur, nor how long the run of different numbers intervening between  “345” and “345” is. Indeed the intervening run may be 0 digits long and you might find “345345”.
Or, an occurrence of “345” is followed by 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9 with approximately random distribution; the last 97 known digits of π might be 6394399712_5311093276_9814355656_1840037499_3573460992-1433955296_8972122477_1577728930_8427323262_4739940 and that sequence might be long enough to occur only once amongst those known digits, but we don't know what follows the last “40”.

That is what I meant about not predictable, and I hope that explanation is clear.“

Stephan van Hulst
Saloon Keeper
Posts: 11877
253
It is, but you're measuring with double standards. If I found A repeating sequence in a rational number, I also can't know if that is actually THE repeating sequence unless I also know the numerator and the denominator and the index of the sub-sequence.

Consider the expansion 0.123777456(777888). If I gave you the sub-sequence 777, would you be able to tell me what the next digit would be, without also knowing the numerator and denominator and the index of the sub-sequence?

Campbell Ritchie
Marshal
Posts: 68862
275
No, but I think it means we aren't actually disagreeing with each other.

 They worship nothing. They say it's because nothing is worth fighting for. Like this tiny ad: Thread Boost feature https://coderanch.com/t/674455/Thread-Boost-feature