Win a copy of Programmers Guide to Apache Thrift this week in the Open Source 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
- Devaka Cooray
- Knute Snortum
- Paul Clapham
- Tim Cooke

Sheriffs:

- Liutauras Vilda
- Jeanne Boyarsky
- Bear Bibeault

Saloon Keepers:

- Tim Moores
- Stephan van Hulst
- Ron McLeod
- Piet Souris
- Frits Walraven

Bartenders:

- Ganesh Patekar
- Tim Holloway
- salvin francis

posted 2 months ago

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.

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

posted 2 months ago

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);

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

posted 2 months ago

- 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.

posted 2 months ago

- 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)⌉`

Every additional binary digit (bit) doubles the range of integers that can be represented. The formula for determining the largest integer

David Gillette

Greenhorn

Posts: 24

1

posted 2 months ago

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?

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

posted 2 months ago

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]

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

posted 2 months ago

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?

posted 2 months ago

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.

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

posted 2 months ago

Fascinating.

posted 2 months ago

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.

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: 10206

216

posted 2 months ago

David Gillette

Greenhorn

Posts: 24

1

posted 2 months ago

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"?

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"?

posted 2 months ago

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.

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.

posted 2 months ago

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

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. ;-)

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Stephan van Hulst

Saloon Keeper

Posts: 10206

216

posted 2 months ago

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.

posted 2 months ago

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.

posted 2 months ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

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.

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: 10206

216

posted 2 months ago

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.

The same is true for rational numbers by the way. If I have the subsequence

[edit]

This was a reply to Campbell.

Campbell Ritchie

Marshal

Posts: 64473

225

posted 2 months ago

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.“

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: 10206

216

posted 2 months ago

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?

Consider the expansion

Campbell Ritchie

Marshal

Posts: 64473

225

posted 2 months ago

No, but I think it means we aren't actually disagreeing with each other.

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!