Well now, this is funny. In writing the paper, I realized something about an older identity that I had found for quotients which appears to be even cheaper than I initially had realized, but my mind was too weak to notice it at the time.
So, obviously, a reciprocal $\frac{1}{y}$ can be represented in base $y$ as $(0.1)_y$. Great.
Converting it to binary is as trivial as computing $2^{k(n)} \bmod y$ where $k(n) = k(n) + 1 | k(0) = 0$. We do this up to $n$ for $n$ bits of precision. If we then evaluate $2(2^{k(n)}\bmod y)$ and it is greater than $y$, then the value of that bit is one, and zero otherwise.
But me and my slow brain just realized that this describes a number $2^{n+1} - 1$.
It's almost possible to just use $(2^{n+1} - 1)\bmod y$ to do this, but it's off by one step. We recognize that $(a + b) \bmod c = ((a\bmod c) + (b\bmod c)) \bmod c$.
In place of the latter, what we have is, for $n$ bits, an expression of the form $(a_0\bmod c) + (a_1\bmod c) + ... + (a_n\bmod c)$.
Wowwww ok so I can literally just compute in hexadecimal to get more throughput (or even base $2^8$ or $2^{16}$ depending on how high we can divide) since the corresponding digit in that base is apparently just the floored quotient $\lfloor\frac{b(b^n \bmod y)}{y}\rfloor$. Using base $2^{16}$ with four execution units, you could get insanely good latency and throughput with integers.
It also would appear that $\frac{1}{y} = \sum_{n=1}^{\infty} (y+1)^{-n}$ just at a glance, but that could be wrong.
This makes sense given what I learned as well about infinite sum representations of a reciprocal in its corresponding integer base, viz. that $(0.1)_y = (0.0(y-1)(y-1)(y-1)(...))_y$ where $AB$ and $(A)(B)$ here specifically represents the concatenation of two integers.
i don't know what rigorous and universal means, but that's a good example. what is a polynomial equation. well, you can pretty much write out what that is.
but other equations that don't fit that definition might be capable of being turned into polynomial equations.
@leslietownes Right, well, a bit of philosophy here is handy. The substance of some mathematical entity is accidental to the form it takes within a potency, formally speaking. Applied to this particular case, that is to say, formally in the language of mathematics, "If an algebraic function $f:\Bbb{R}\to\Bbb{R}$ can be written as a polynomial of at most degree one [has at most one real root], then it is linear." as just one possible definition.
the complication with differential equations is that to get good thoerems you often need to make at least some assumptions on the functions you're working with. but the obvious sets of assumptions either don't work, or are far too restrictive in terms of what you want to do, or don't give you good theorems.
which is why the papers on the differential equations oriented parts of the arxiv are littered with different function spaces, chosen for whatever the people interested in them are working on.
@leslietownes Leslie: I took a look at the linear ode definition again and again and concluded that. We say that $y’+a(x)y=b(x)$ is linear if a and b are continuous.
it's sort of a 'classical' definition, where people wuld classify equations according to what they looked like and maybe the abstract notion of linear map didn't even really have cachet yet
If I had a piecewise differentiable function with discontinuities at arbitrary points, am I to say that it is simply non-linear, or rather, might we say that it's better to say "The function is linear everywhere except ..."?
I would say the latter is perhaps more useful under that definition of linear.
rb this sounds like a coding thing. ie one might have to know what language you are writing in, how you are storing this stuff in data structures, how you are displaying it to screen or writing it to a file. are you running it on your phone with 20,000 apps open. the math might not be the half of it.
@leslietownes No, no, I'm just thinking about a good algorithm. The ball's path is governed by the law of reflection, so that's how I'm doing it right now. I define an initial $(P_0,V_0)$ and once the ball hits a wall, I just make its velocity vector reflect. I'm wondering if you all have any better ideas.
GPUs are not well-suited to recursion. If you're writing anything iterative in a GPU shader, that could be a cause. Still, this is all just very poor speculation without anything more concrete about how you are performing these computations.
i mean, from a starting P,V one thing you could do is generate the sequence of points that it hits the walls at. so don't think about the path, just think of the points that would be drawn on the walls if the ball had ink.
computing that sequence of points might be as easy, or easier, than animating the thing. you know where that ball is going. not a lot is happening to that velocity.
If you're going to have an iterative process in the GPU, convert it to a function of time instead, or do the iterating on the CPU and send the result to the shader.
@AMDG I understand that even “solution” of an ode has a meaning in the sense that it must be defined on an interval. So we may restrict non-linear/linear definition to an interval, I guess.
@leslietownes Thank you for the suggestion. The thing is that I actually do care about the path ... I'm looking for a periodic path and so the ball's trajectory does indeed play a role, at least for me.
Essentially, the ball behaves like a beam of light, reflecting off the walls just like a light beam would.
rb: sorry. i didn't mean "you don't care about the path" so much as, if you're modeling this thing with short time increments and in most of those increments nothing happens to the velocity, another way to do it would be to precompute just the set of points where things do happen with the velocity.
It would seem that your problem which you intend to solve is, "Given an initial point and initial vector, and a set of surfaces which transform this vector, is the path traced by this vector over time cyclic?"
There’s a nice approach to this problem that uses vector cross products. Define the 2-dimensional vector cross product v × w to be vx wy − vy wx.
Suppose the two line segments run from p to p + r and from q to q + s. Then any point on the first line is representable as p + t r (for a scalar pa...
It's not the interpreter -- it's my algorithm, which, as @leslietownes nicely put it, spends a lot of time modeling the ball even when nothing's happening to its velocity.
I'm running a while loop that checks (every 1/1000th of a second, I believe) if the ball is hitting a wall. If not, keep going. If it is, reflect using $\theta_i=\theta_r$
try parametrizing past, now; incomingVector appears to be instantiating an object every frame even though you are only modifying pos and axis; same issue with perp and reflectedVector. Refactor those and try again.
I doubt it's a memory leak, but memory leaks rarely are the cause of bad performance from cache misses unless you're doing something insane like creating a new page every time an object is instantiated and the heap is so fragmented that you get at least one cache miss every frame.
I don't see how. There's very little information available, especially given that I don't know Python very well at all (in terms of library calls). The best I have is some speculations about what is going on here, such as whatever the arrow function is doing. It has the form of an initializer, so I assume it is an initializer; if the interpreter reads to and from the array all the time, then parametrizations ensure everything stays in cache longer; etc.
@rb3652 Just as a rule of thumb, the more algorithmic and pure your function is, the more it should be parametrized in order to keep things neater and hopefully stay in cache more instead of dereferencing globals. This will also make debugging much easier since you can just look at the function itself without having to scroll to where you defined something.
It also helps to keep procedures decoupled from particular implementation details.
In addition, pay attention to wherever memory is being allocated and data objects are being initialized. Don't make copies without necessity. Use as little memory as possible.
Basically optimization today is just about memory and little else. If you want to optimize an algorithm, the latency is still important and must not be neglected, but memory is the primary bottleneck in most applications.
(This is for CPU-side on contemporary x86 microarchitectures, not GPU-side code. GPU is different.)
Not much. I've spent much of my time in software design and studying contemporary hardware, however, as opposed to writing software which is the easy part and makes up much less than half the time spent in making software.
The majority of software production is design and error correction.
The most hands-on I've got is with writing Minecraft shaders.
But it isn't like it's difficult to grasp vector algorithms and operations...
Sequential execution is one dimensional; parallel execution is two dimensional.
$U_n$ is multiplicative group of integers modulo $n$.
and is of order $\phi(n)$.
I didn't know the former symbol $(Z/{nZ})^*$ earlier.
I am familiar with $U_n$ though.
Any idea on how to show $\sum_{r=1}^{p^n-1}\binom{p^n-1}{r}p^r$ is divisible by $p^n$, where $p$ is an odd prime and $n\ge 1$ is a natural number? Induction is not allowed.
Aight, it's late here, and I can't make up my mind on whether or not to go to bed, but I have two words to say before I leave for now: deterministic threading.
Now that I think of it, I should really change my profile picture to a pig because I find myself more dumber than a baby. Also Now I realized that I am too braindead to study pure mathematics and computer science&programming. The only thing I seem to be capable of is following robotic instructions and pumping my bicycle.
There is a system of linear inequalities bounded on both sides. Are there methods for analytically solving such inequalities? Is it possible to use the inversion of the coefficient matrix A in the solution process?
But I know Legendre formula (de-Polignac's formula) that you mentioned in your answer, although in a different form.
Different in the sense that the version that I know doesn't involve $\sigma$.
The version that I'm familiar with: If $p$ is a prime then $\sum_{i=1}^\infty \lfloor \frac n{p^i}\rfloor=:a$ is number such that $p^a$ divides $n!$ but $p^{a+1}$ does not divide $n!$.
I'll try understanding your way also professor Rob. Thanks. Meanwhile, I'm posting the question on mse also because the question has a group theoretic flavour to it. Also, the question is from Dummit and Foote's.
@AlessandroCodenotti a closed base satisfying certain properties. What you do is define a space of ultrafilters using this base, and then topology on the space of those ultrafilters
It's what you can find online about Cech-Stone compactifications, but the method is more refined, and actually gives you all possible (separable, metrizable) compactifications
Let $p_1 = 1, p_2 = 3, p_3 = 5,...$ where the sequence $p_n$ is $1$ and the odd primes ordered by size.
Let $Re(s),Re(z) > 0$.
define $g(z,s) =\sum_{n=1}^{\infty} (-1)^{n+1} \dfrac{z^n}{p_n^s}$
Notice this sequence diverges for $Re(z) > 1$ but we use analytic continuation to define it there.
What...
What's the fastest way to improve mathematical maturity? Learning harder and more advanced mathematics or learning to solve harder and harder problems? I feel like my mathematical maturity is improving, but not at a fast enough rate.
in the real numbers we get rid of that problem by requiring the square root to be non-negative, and there's a way of doing that for complex numbers too, but then it isn't always true that $x^ay^a=(xy)^a$
@LearningCHelpMeV2 What's your context? Are you an undergrad?
It is true that $i. i$ is a square root of $-1\times -1 = 1$. Simply it isn't the square root of $1$ as you commonly know it. Indeed any complex number has two square roots. When dealing with positive real numbers, there is a consistent choice to make, by taking the positive square root. And it turns out that this choice is consistent with the product rules $\sqrt{a}\sqrt{b} = \sqrt{ab}$
@LearningCHelpMeV2 pick up a book on a topic and read it. I suggest Spivak's Calculus. You'll be better prepared than most of your classmates. Try focusing on learning techniques
@123 I have to leave now, but write out which part you're having trouble with
By definition, $i^2 =-1$, not $i^2=1$. That is either precisely the definition of $i$, or follows immediately from however you choose to define the complex numbers.
This isn't a law or theorem---it is simply the definition.
Yeah, exponentiation is not commutative for the complex numbers, meaning that it is not necessarily true that $(z^a)^b=(z^b)^a$. This has always broken my mind, too, because it does respect multiplication. Like $(z^a)^b=z^{ab}$, iinm, but it's just that $z^{ab}$ can have multiple possible answers.
Any ideas how I can tackle the limit of $n\rightarrow\infty \abs{a_n/a_{n+1}}$?
It's a... limit of a fraction of sums I guess
To be clear I also thought about how to post this on the main site, but I've not yet passed the staring phase so I have very little work to show meaning the question will not be very good
The $lambda_{kj}$ should be $lambda_\ell - \lambda_j$, the $k$ shouldnt be there at all (to avoid confusion with the index of the sum)
I got it now. For $n=1$, $(1+p)^{p^{n-1}}\equiv \pmod{p^n}$ is true. So suppose that $n\ge 2$. Now suppose that our induction hypothesis is: $(1+p)^{p^{n-2}}\equiv \pmod{p^{n-1}}$. It follows that $(1+p)^{p^{n-2}}=1+k p^{n-1}\implies ((1+p)^{p^{n-2}})^p=(1+p)^{p^{n-1}}=1+\sum_{j=1}^p\binom {p}{j}(kp^{n-1})^j$
(By binomial theorem)
$\ddot\smile$
So we conclude that $(1+p)^{p^{n-1}}\equiv 1 \pmod{p^n}$ for every odd prime $p$ and $n\ge 1$. $\ddot\smile$
on the wikipedia page for ramsey's theorem (https://en.wikipedia.org/wiki/Ramsey%27s_theorem#2-colour_case) they state: It is clear from the definition that for all n, R(n, 2) = R(2, n) = n.
shouldn't it be R(n, 2) = R(2, n) = **2**? Because any coloring of the complete graph with two vertices K_2 yields a subgraph (K_2 itself) where exactly 2 vertices are either red or blue?
vrouvrou just a word of warning. problems like these are fairly difficult to approach from first principles. they often appear in textbooks after some big theorem about existence and uniqueness has been proved. the hypotheses of these theorems vary, so it's possible that someone may answer with a technique that doesn't quite match what you are familiar with.
if you do know of some big theorem on existence and uniqueness, it might help to state what it is, and point out where you encounter difficulty applying it. that might lead to more focused answers.
vrouvrou: sites.oxy.edu/ron/math/341/10/ws/05.pdf ("existence of a unique solution") is the kind of theorem i am thinking of. often these problems are solved by using something like that as a black box.
your problem can be solved in this way, but it would help to know the context of the problem. i.e. what 'can you use' and what would you have to prove.
ted: it's doing better than ever. it is more valuable than ever in times of uncertainty.
Leslie, I’ve been at that question for a long time (background: an exercise problem from Dummit and Foote). I even posted my question on mse on that but it seemed to that that I was not going to get an answer to my question so I deleted that.
koro: i was kidding. :) i do think it's helpful for people to provide new answers to the same question, even if the question is very old. it avoids duplicates and cross-talk between near-duplicates.
@CroCo Why are you doing the computation? Do you know about dimension? If not, the column space of a $3\times 2$ matrix can never be all of $\Bbb R^3$. If the augmented matrix $[A|b]$ has rank $3$, that happens only when the equation $Ax=b$ is inconsistent.
@TedShifrin yes this is the way I understand it but I'm trying to understand the point of this question which is by the way from A Modern Introduction to Linear Algebra by Henry Ricardo.
The book introduces the spanning sets before dimensions.
I don't know the book, so it's hard to say. They want students to develop intuition for dimension before getting there? I have questions like this in my book(s), but mostly after the discussion of $Ax=b$ and consistency.