Win a copy of Serverless Applications with Node.js this week in the NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Liutauras Vilda
  • Bear Bibeault
  • Jeanne Boyarsky
  • paul wheaton
Sheriffs:
  • Junilu Lacar
  • Paul Clapham
  • Knute Snortum
Saloon Keepers:
  • Stephan van Hulst
  • Ron McLeod
  • Tim Moores
  • salvin francis
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Vijitha Kumara

For any integer, n, predict the binary string length, x  RSS feed

 
Greenhorn
Posts: 24
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 24
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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);
 
Sheriff
Posts: 24295
55
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 9997
208
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 24
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 24
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 24
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 24295
55
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 24
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fascinating.
 
Paul Clapham
Sheriff
Posts: 24295
55
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 9997
208
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
David Gillette
Greenhorn
Posts: 24
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 24295
55
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12734
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 9997
208
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 63837
209
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12734
51
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 9997
208
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

[edit]

This was a reply to Campbell.
 
Campbell Ritchie
Marshal
Posts: 63837
209
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 9997
208
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 63837
209
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No, but I think it means we aren't actually disagreeing with each other.
 
"I know this defies the law of gravity... but I never studied law." -B. Bunny Defiant tiny ad:
Create Edit Print & Convert PDF Using Free API with Java
https://coderanch.com/wiki/703735/Create-Convert-PDF-Free-Spire
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!