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 101787 times)

0 Members and 1 Guest are viewing this topic.

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 553
  • Shuffle iT Username: Cuzz
  • Respect: +904
    • 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: 3389
  • Multiediting poster
  • Respect: +3733
    • 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: 553
  • Shuffle iT Username: Cuzz
  • Respect: +904
    • 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: +171
    • 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: 1025
  • Shuffle iT Username: heron
  • Respect: +1148
    • View Profile
Re: Maths thread.
« Reply #1029 on: June 24, 2019, 08:49:17 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.

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: 4198
  • Shuffle iT Username: sty.silver
  • Respect: +1845
    • 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: 553
  • Shuffle iT Username: Cuzz
  • Respect: +904
    • 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: 4198
  • Shuffle iT Username: sty.silver
  • Respect: +1845
    • 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: 2127
  • Respect: +2666
    • 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: 1025
  • Shuffle iT Username: heron
  • Respect: +1148
    • 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

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4198
  • Shuffle iT Username: sty.silver
  • Respect: +1845
    • View Profile
Re: Maths thread.
« Reply #1035 on: July 28, 2019, 12:23:04 pm »
0

Is there a name for this matrix?

[1,1,1,1,1
 1,2,4,8,16
 1,3,9,27,81
 1,4,16,64,256
1,5,25,125,625]

If you have a polynomial of degree 5 and evaluate it at positions 1 through 5, this is the coefficient matrix. I thought this was an important matrix with a name and prob a wikipedia article, but I can't find it.
Logged

faust

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2556
  • Shuffle iT Username: faust
  • Respect: +3531
    • View Profile
Re: Maths thread.
« Reply #1036 on: July 28, 2019, 12:30:03 pm »
+1

Is there a name for this matrix?

[1,1,1,1,1
 1,2,4,8,16
 1,3,9,27,81
 1,4,16,64,256
1,5,25,125,625]

If you have a polynomial of degree 5 and evaluate it at positions 1 through 5, this is the coefficient matrix. I thought this was an important matrix with a name and prob a wikipedia article, but I can't find it.

It the Vandermonde matrix for the tuple (1,2, ..., n).
Logged
Since the number of points is within a constant factor of the number of city quarters, in the long run we can get (4 - ε) ↑↑ n points in n turns for any ε > 0.

silverspawn

  • Governor
  • *****
  • Offline Offline
  • Posts: 4198
  • Shuffle iT Username: sty.silver
  • Respect: +1845
    • View Profile
Re: Maths thread.
« Reply #1037 on: July 28, 2019, 01:28:10 pm »
0

Yes! Thanks.
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2641
    • View Profile
Re: Maths thread.
« Reply #1038 on: August 06, 2019, 09:27:39 pm »
0

How would you describe math to a layperson, in such a way as to try to break through their preconceived notions of what it is?
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

Awaclus

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 11198
  • Shuffle iT Username: Awaclus
  • (。 ω 。`)
  • Respect: +11878
    • View Profile
Re: Maths thread.
« Reply #1039 on: August 06, 2019, 09:53:51 pm »
0

How would you describe math to a layperson, in such a way as to try to break through their preconceived notions of what it is?

What are their preconceived notions of what it is?
Logged
Bomb, Cannon, and many of the Gunpowder cards can strongly effect gameplay, particularly in a destructive way

The Twitch channel where I stream DominionThe YouTube channel where I make musicDownload my band's albums for free

theorel

  • Navigator
  • ****
  • Offline Offline
  • Posts: 77
  • Shuffle iT Username: theorel
  • Respect: +44
    • View Profile
Re: Maths thread.
« Reply #1040 on: August 08, 2019, 08:54:58 am »
0

How would you describe math to a layperson, in such a way as to try to break through their preconceived notions of what it is?

My go-to answer to the question of "what is math?" was "the study of abstractions".
Then, if they actually wanted more information, I would explain how numbers are an abstraction of quantities of things, and arithmetic is an abstraction of counting, and algebra is an abstraction of arithmetic.  (by actually explaining it, y'know, anything you do with 3 and 4 applies to all instances of 3 things and 4 things, etc).

Once I hit algebra, most laypeople would note how they never really understood algebra, and the conversation would move on...but generally this would help those people stop thinking that I did some sort of "advanced arithmetic" or numerology or something.

For the non-maths people that actually understood Calculus, this also offered a nice framework if we continued the discussion with something like, "so what is topology?"
« Last Edit: August 08, 2019, 08:56:19 am by theorel »
Logged

Cuzz

  • Minion
  • *****
  • Offline Offline
  • Posts: 553
  • Shuffle iT Username: Cuzz
  • Respect: +904
    • View Profile
Re: Maths thread.
« Reply #1041 on: August 08, 2019, 10:40:43 am »
+1

How would you describe math to a layperson, in such a way as to try to break through their preconceived notions of what it is?

This doesn't precisely answer the question, but this classic essay by Thurston is a great read

https://arxiv.org/pdf/math/9404236.pdf
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2641
    • View Profile
Re: Maths thread.
« Reply #1042 on: August 08, 2019, 08:08:18 pm »
0

How would you describe math to a layperson, in such a way as to try to break through their preconceived notions of what it is?

My go-to answer to the question of "what is math?" was "the study of abstractions".

So Picasso is math?  (joking, although I usually say "the study of logical abstractions")
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm
Pages: 1 ... 40 41 [42]  All
 

Page created in 0.087 seconds with 22 queries.