How to compute log919(2^82589933 − 1)?

taf · December 16, 2020, 11:08am

i am not really sure how to compute this

using:

google/guava/blob/master/guava/src/com/google/common/math/BigIntegerMath.java

/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.math;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.math.MathPreconditions.checkNonNegative;
import static com.google.common.math.MathPreconditions.checkPositive;

This file has been truncated. show original

i can do base 2 and 10 but not 919…

any ideas?

generateme · December 17, 2020, 5:52pm

Just change base of your log919.

log919(x) = log2(x) / log2(919) = log10(x) / log10(919) = ln(x) / ln(919)

taf · December 16, 2020, 12:58pm

in theory this looks good, but how can i do it in practice?

generateme · December 17, 2020, 5:52pm

I don’t know. 2^82589933 has around 2.5e7 digits. Without -1 it’s fairy simple and can be done in double (using property of logarithm of power). Also, the difference between log919(2^82589933 − 1) and log919(2^82589933) is very, very small.

taf · December 16, 2020, 4:32pm

first of all thx for helping me out! much appreciated!

still i’ll have to think about it for a bit

taf · December 17, 2020, 4:55am

I don’t know. 2^82589933 has around 2.5e7 digits. Without -1 it’s fairy simple and can be done in double (using property of logarithm of power). Also, the difference between log919(2^82589933 − 1) and log919(2^82589933) is very, very small.

i slept it over… but i still don’t get it

but using:

i can do it:

8389942.642…

but i am still very unhappy about the time it takes me to compute it! ( my first attempt to compute this took 4 minutes! )

now if i simply and naively enter the math into wolfram alpha:

log(2^82589933 − 1)/log(919)

it spits out the result pretty quick…

what am i missing here? any ideas?

John_Shaffer · December 17, 2020, 5:52pm

Understanding when to use approximation is very important in this kind of calculation. Wolfram probably knows when an approximation will give the same answer, and uses that. log(2^82589933 - 1)/log(919) - log(2^82589933)/log(919) gives 0 in Wolfram Alpha. Wolfram gives the same answer as we get in Clojure, only with more digits:

(* (Math/log 2) 82589933 (/ (Math/log 919)))
;= 8389942.642742455

I’m sure you can calculate the accuracy of the approximation if you need to. It’s probably accurate to far more than 100 digits.

taf · December 17, 2020, 5:52pm

oh now i get it! ( kind of embarrassing that it would take me this long, after @generateme had already given me all that help! )

anyway, thank you very much for your explanation / patience! i really do appreciate it!

generateme · December 17, 2020, 11:25pm

I didn’t want to give you an actual solution

Just to emphasize why -1 is numerically not important, imagine that you calculate previous power of 2, ie. 2^82589932. The difference between 2^82589933 and 2^82589932 equals… 2^82589932 - which is huuuuge! Compare it with -1. And when you apply logarithm to and take the difference you get 0.1. Such huge step (2^82589933) under logarithm, gives just 0.1. So difference of -1 is actually meaningless.

taf · December 18, 2020, 5:15am

yeah, now feels like things are starting to make a bit more sense

idk, for some reason i just didn’t see that i do not actually need to compute this largest of known prime numbers in the first place! … since… well since it is basically given as a power of 2, therefore i do already have the log2 of it in hand!

so:

log919(2^82589933 − 1) = ( for all practical intents and purposes ) log919(2^82589933) = log2(2^82589933) / log2(919) = 82589933 / log2(919) = 8389942.6427…

now seams to me that i can take away a couple of things from this:

really good refresher on how log works
explored some libs for dealing with huge numbers
got reminded that some / often times i am a bit of a doofus
got reminded that asking for help ( although slightly unpleasant / embarrassing ) is, more often than not, by far the smartest course of action!

vvvvalvalval · December 19, 2020, 6:13pm

@taf out of curiosity, what motivated the use of base-919 logarithm? Seems uncommon

Btw: another frequently useful property of the natural logarithm is the approximation ln(1+x) ~ x for very small x. (From which you can deduce that ln(A + B) ~ ln(A) + B/A if B << A, which can be used to quantify @John_Shaffer’s point about approximation accuracy).

taf · December 19, 2020, 8:22pm

what motivated the use of base-919 logarithm?

so i was doing a few of these advent of code puzzles… got a bit interested in the entire puzzle thing… and found the following very cool site:

so now i am doing a few of those as well… and that got me started thinking about prime numbers a bit… and more such math related things… wondering if perhaps i should try to come up with a little programming puzzle myself…

anyway… long story short… i ended up having a possibly cute little idea for how one could write a program for turning a large prime number into… well… kind of a pictorial ascii-art rendition thereof…

now… 919 is also prime and also a numeric palindrome… so it seamed to fit in well with the rest of my weird scheme