Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 40 41 [42]  All

Author Topic: Maths thread.  (Read 98626 times)

0 Members and 1 Guest are viewing this topic.

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 552
  • Shuffle iT Username: Cuzz
  • Respect: +902
    • View Profile
Re: Maths thread.
« Reply #1025 on: June 24, 2019, 07:03:11 pm »
+1

People were able to compute plenty of derivatives perfectly well far before any of the modern rigorous notions of limits, which was primarily due to Cauchy. They did so mostly with "handwaving."

The key issue here is more subtle, and it's more about being circular than being handwavy. The approximation e^h = 1+h when h is small is only valid for the number e. It's equivalent to the fact that the tangent line to the graph of e^x at x=0 is y=1+x, which can't be established without knowing that the derivative of e^x is e^x in the first place.
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3386
  • Multiediting poster
  • Respect: +3719
    • View Profile
Re: Maths thread.
« Reply #1026 on: June 24, 2019, 07:10:31 pm »
0

The substitution step could be done rigorously if you use the infinite series definition of the exponential. That would give a different result if you have a number other than e.

I think without the infinite series definition of the exponential function (or the definition as the inverse of the logarithm), the farthest you can go with this is that the derivative of exp is proportional to exp.

EDIT: what cuzz said
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 552
  • Shuffle iT Username: Cuzz
  • Respect: +902
    • View Profile
Re: Maths thread.
« Reply #1027 on: June 24, 2019, 07:23:25 pm »
+1

The substitution step could be done rigorously if you use the infinite series definition of the exponential. That would give a different result if you have a number other than e.

I think without the infinite series definition of the exponential function (or the definition as the inverse of the logarithm), the farthest you can go with this is that the derivative of exp is proportional to exp.

EDIT: what cuzz said

Right, I claimed that you can't use that substitution without already knowing the derivative of e^x is itself, but in fact you can if you define the exponential function as its Maclaurin series. But then the fact that the derivative of the function defined by 1+x+x^2/2 + x^3/6 + ... is itself is completely trivial via term-by-term differentiation (modulo the fact that you'd need to prove or just accept both that the series converges and that functions defined by power series are differentiable term-by-term).

In fact, it's worth thinking about what your original definition of the exponential function even is, as this can make a difference as to whether any given fact about it is a theorem or a tautology. For example, it's also perfectly reasonable to define the exponential function as the unique function satisfying f'(x) = f(x) and f(0) = 1, once you prove that such a function exists and is unique.
Logged

hhelibebcnofnena

  • Apprentice
  • *****
  • Offline Offline
  • Posts: 290
  • Respect: +166
    • View Profile
Re: Maths thread.
« Reply #1028 on: June 24, 2019, 08:40:18 pm »
0

People were able to compute plenty of derivatives perfectly well far before any of the modern rigorous notions of limits, which was primarily due to Cauchy. They did so mostly with "handwaving."

The key issue here is more subtle, and it's more about being circular than being handwavy. The approximation e^h = 1+h when h is small is only valid for the number e. It's equivalent to the fact that the tangent line to the graph of e^x at x=0 is y=1+x, which can't be established without knowing that the derivative of e^x is e^x in the first place.

Still not quite sure I understand. Doesn't x^h approach 1+h as h approaches 0 for any positive x?

The "handwaving" is just a less formal way of talking about limits, right?
« Last Edit: June 24, 2019, 08:41:23 pm by hhelibebcnofnena »
Logged
Hydrogen Helium Lithium Beryllium Boron Carbon Nitrogen Oxygen Fluorine Neon Sodium

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1024
  • Shuffle iT Username: heron
  • Respect: +1147
    • View Profile
Re: Maths thread.
« Reply #1029 on: June 24, 2019, 08:49:17 pm »
0

People were able to compute plenty of derivatives perfectly well far before any of the modern rigorous notions of limits, which was primarily due to Cauchy. They did so mostly with "handwaving."

The key issue here is more subtle, and it's more about being circular than being handwavy. The approximation e^h = 1+h when h is small is only valid for the number e. It's equivalent to the fact that the tangent line to the graph of e^x at x=0 is y=1+x, which can't be established without knowing that the derivative of e^x is e^x in the first place.

Still not quite sure I understand. Doesn't x^h approach 1+h as h approaches 0 for any positive x?

The "handwaving" is just a less formal way of talking about limits, right?

It actually approaches 1 + hlogx. But since log(e) = 1, for e^h it is 1 + h.

Edit: Well, you can say that lim as h-->0 of | x^h - (1 + h) | = 0. But that is only because both of the quantities approach 1. It is more meaningful to consider the difference relative to h, which just gives the limit of the derivative: (x^h - (1 + h)) / h
« Last Edit: June 24, 2019, 08:51:17 pm by heron »
Logged

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4189
  • Shuffle iT Username: sty.silver
  • Respect: +1843
    • View Profile
Re: Maths thread.
« Reply #1030 on: June 25, 2019, 03:20:25 am »
0

People were able to compute plenty of derivatives perfectly well far before any of the modern rigorous notions of limits, which was primarily due to Cauchy. They did so mostly with "handwaving."

The key issue here is more subtle, and it's more about being circular than being handwavy. The approximation e^h = 1+h when h is small is only valid for the number e. It's equivalent to the fact that the tangent line to the graph of e^x at x=0 is y=1+x, which can't be established without knowing that the derivative of e^x is e^x in the first place.

I don't think that's a different issue from what I said. Being handwavy is what allows the argument to get away with whatever wrong thing it's actually doing, like being circular. If it spelled out the argument explicitly, we would see what exactly it relies on.

Taking shortcuts is never a mistake in itself, it's always a black box where real mistakes may or may not be hiding.
Logged

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 552
  • Shuffle iT Username: Cuzz
  • Respect: +902
    • View Profile
Re: Maths thread.
« Reply #1031 on: June 26, 2019, 08:40:26 pm »
0

People were able to compute plenty of derivatives perfectly well far before any of the modern rigorous notions of limits, which was primarily due to Cauchy. They did so mostly with "handwaving."

The key issue here is more subtle, and it's more about being circular than being handwavy. The approximation e^h = 1+h when h is small is only valid for the number e. It's equivalent to the fact that the tangent line to the graph of e^x at x=0 is y=1+x, which can't be established without knowing that the derivative of e^x is e^x in the first place.

I don't think that's a different issue from what I said. Being handwavy is what allows the argument to get away with whatever wrong thing it's actually doing, like being circular. If it spelled out the argument explicitly, we would see what exactly it relies on.

Taking shortcuts is never a mistake in itself, it's always a black box where real mistakes may or may not be hiding.

My point was just that the answer the question:

The physicist's proof for the derivative of ex:

(ex + h - ex)/h = ex(eh - 1)/h.  Because h is small, eh = 1 + h, so ex(eh - 1)/h = ex(1 + h - 1)/h = ex(h/h) = ex.

What prevents that from working with any number other than e?

is something we can specifically identify in the argument. It's exactly contained in the statement "Because h is small, eh = 1 + h." It's not just a "there's some handwaving so it's all completely invalid" kind of thing.
Logged

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4189
  • Shuffle iT Username: sty.silver
  • Respect: +1843
    • View Profile
Re: Maths thread.
« Reply #1032 on: June 27, 2019, 04:00:26 am »
0

Yeah, no doubt your answer was better / more specific.
Logged

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2116
  • Respect: +2642
    • View Profile
Re: Maths thread.
« Reply #1033 on: June 27, 2019, 02:43:01 pm »
0

I need help figuring out the RNG reverse engineering described here



The paper deliberately skips over the number theory itself, so it's been tricky figuring out the exact problem they're considering. Here's my understanding so far.
  • Paper Mario's RNG is of the form RNG(t+1) = (a * RNG(t) + b) mod 2^32 where a, b are odd numbers.
  • This RNG is cyclic and visits each of the 2^32 possible RNG numbers in some order before repeating.
  • Let's define RNG(0) = 0. If we have RNG(0) = 0, then RNG(1) = b, RNG(2) = ab +b , RNG(3) = a^2b + ab + b, and in general RNG(n) = b * (a^n -1) / (a - 1) mod 2^32, so we can compute the RNG for arbitrary offsets in closed form. In practice the RNG is actually initialized to 1, but since the sequence is cyclic, we can simply redefine the start point as the point where the RNG = 0.
  • By inverting the RNG algorithm (solving RNG(n) = b * (a^n - 1) / (a-1) mod 2^32 for n), we can find exactly where in the sequence we currently are, and how many steps in the sequence we need to advance to manipulate desired RNG outcomes.

The part where I'm lost is inverting the RNG algorithm. If you look at the pseudocode of the algorithm, it eventually reduces to solving a^n = c mod 2^32 for an a = 1 mod 4. This is discrete log which is hard in general, but is apparently solvable in mod 2^32 as follows.

  • Let v2(x) = the 2-adic valuation of x (the largest k such that 2^k divides x and 2^{k+1} does not divide x. Commonly v2(0) = infinity
  • Assume v2(a-1) = v2(c-1) (code does not work if this is not true).
  • Let n_guess be our current guess of the exponent with n_guess = 0.
  • For each power of 2 (from 2^0 to 2^31), compare v2(a^{n_guess + 2^k} - c) to v2(a^{n_guess} - c). If the 2-adic valuation is larger with the power of 2, add 2^k to n_guess.
  • After doing so we have n_guess = the n that solves a^n = c mod 2^32.

The video says you prove this works using the Lifting the Exponent Lemma but I don't understand how you apply it.
Logged
I have a blog! It's called Sorta Insightful. Check it out?

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1024
  • Shuffle iT Username: heron
  • Respect: +1147
    • View Profile
Re: Maths thread.
« Reply #1034 on: June 28, 2019, 08:51:54 pm »
0

Sorry this explanation is kind of poorly written.

Note that for x coprime to 2^32, x^(2^30) = 1 mod 2^32.

Suppose that a has maximum order, i.e. a^k ≠ 1 for 0 < k < 2^30.
Let n = c0 + c1*2 + c2*2^2 + ... + c29*2^29.
(a^n)^(2^29) = c^(2^29)
so
a^(c0 * 2^29) = c^(2^29)
Since a has maximum order, exactly one of c0 = 0 and c0 = 1 will work. And then you can proceed like that to find the other ci.
So where does LTE come in?

Well, since a and c are both 1 mod 4, v2((a^c0)^(2^29) - c^(2^29)) = v2(a^c0 - c) + v2(2^29).
We know the LHS is either 32 or <32 depending on choice of c0. So RHS is either 3 or <3 depending on choice of c0.
Similar argument applies for other ci.

Why v2(a-1) = v2(c-1)?
Well, earlier I had this assumption that a had maximal order. That may not be true. However, if a = 1 mod 4, then o(a) = 32 - v2(a - 1).
So a and c have the same order.
Let that order be 2^h.
Then we can do stuff like
a^(c0*2^(h-1)) = c^(2^(h-1)) for exactly one choice of c0.
Logged
Pages: 1 ... 40 41 [42]  All
 

Page created in 0.087 seconds with 21 queries.