you have
f(0) = 0
f(2n + 1) = 2 * f(n) + 1
f(2n + 2) = f(n+1) + f(n) + 1
f(n)=n looks like a solution to me
Forum Index > General Forum |
Liebig
France738 Posts
you have f(0) = 0 f(2n + 1) = 2 * f(n) + 1 f(2n + 2) = f(n+1) + f(n) + 1 f(n)=n looks like a solution to me | ||
Deleted User 3420
24492 Posts
On June 17 2017 05:39 hypercube wrote: Did you try some numerical experiments? Are you interested in an exact expression or only asymptotic behaviour? The second one seems to be just on the order of n. I am starting to think there isn't a reasonable way to get the exact expression. I've looked analysis of this algorithm up online and there doesn't seem to be any exact analysis online. This is actually an analysis of best case quicksort comparisons that I am trying to do, if you are familiar. I can see conceptually how this would be in the ballpark of n, but can you show the math for that? Also I solved the actual values for 1 to 20. Itst a bit odd. nowhere near n for low values. On June 17 2017 05:47 Liebig wrote: let f(n) be the result of your weird stuff for n you have f(0) = 0 f(2n + 1) = 2 * f(n) + 1 f(2n + 2) = f(n+1) + f(n) + 1 f(n)=n looks like a solution to me I've never seen recursion used this way, gonna take a minute to wrap my head around this lol edit: ok I get it. that's neat, But I am not as quick as you in using it to analyze the outcome | ||
Acrofales
Spain17186 Posts
On June 17 2017 05:47 travis wrote: Show nested quote + On June 17 2017 05:39 hypercube wrote: Did you try some numerical experiments? Are you interested in an exact expression or only asymptotic behaviour? The second one seems to be just on the order of n. I am starting to think there isn't a reasonable way to get the exact expression. I've looked analysis of this algorithm up online and there doesn't seem to be any exact analysis online. This is actually an analysis of best case quicksort comparisons that I am trying to do, if you are familiar. I can see conceptually how this would be in the ballpark of n, but can you show the math for that? Show nested quote + On June 17 2017 05:47 Liebig wrote: let f(n) be the result of your weird stuff for n you have f(0) = 0 f(2n + 1) = 2 * f(n) + 1 f(2n + 2) = f(n+1) + f(n) + 1 f(n)=n looks like a solution to me I've never seen recursion used this way, gonna take a minute to wrap my head around this lol Well, it's m, such that m+1 is the greatest power of 2 less than n. However, add 1 for every power of 2 you encounter along the way. For instance n=16 has 8 sublists of size 2 (or greater), rather than 7. How many powers of 2 you'll encounter is hard to predict, but if you want asymptotic behaviour, take a completely absurd upper bound: say you have all m sublists with a size equal to a power of 2 (iow, all your sublists), even that would only give you 2m total lists (and is completely impossible), which is still O(n). | ||
Simberto
Germany11032 Posts
On June 17 2017 05:39 hypercube wrote: Did you try some numerical experiments? Are you interested in an exact expression or only asymptotic behaviour? The second one seems to be just on the order of n. Asymptotic is definitively at most order of n. We can easily get an upper limit, because the kth step (with 0 being the initial set) produces <= 2^k new groups of numbers, and there are < log 2 (n) steps. Thus, there are definitively < Sum from 0 to log2(n) (2*k) = 2^(log2(n) + 1)-1 = 2n-1 total sets in this algorithm. An exact number is going to be harder to get. | ||
Liebig
France738 Posts
cause for n = 1, you should have 0 according to your rules, hmm f(0) = 0 f(1) = 0 f(2) = 1 for n > 0, f(2n + 1) = 2 * f(n) + 1 for n > 0, f(2n + 2) = f(n+1) + f(n) + 1 f(n) = n doesn't work there, let me think a bit | ||
Deleted User 3420
24492 Posts
"What is the fewest exchanges that the algorithm will execute for an input of size n. No justification needed." (What we have been doing demonstrates the best case for exchanges) In exact counts, with n elements, if n =3 we do only 1 exchange. If n = 7, we do only 3 exchanges. if n = 15, we do 7 exchanges. After that it is always worse than this. So does that mean that a technically correct answer to this question is: "(the floor of n/2) - 1" ? | ||
Amanebak
Czech Republic528 Posts
On June 17 2017 05:42 Simberto wrote: Show nested quote + On June 17 2017 04:53 Amanebak wrote: Hey. I stumbled across a problem like this: What is the longest gondola that can take a right-angle turn of a Venetian canal? The width of the canal is 2, respectively 3 length units before, resp. after the turn. I apologize for my English. Unless i missed something, the result is 5*sqrt(2). The gondola needs to be able fit into the diagonal of the (2+3)*(2+3) square, which has a length of 5 sqrt (2) At that point, 2sqrt(2) of the gondola is in the thinner canal, and 3sqrt(2) is in the thicker canal. It is obvious that no longer gondola could reach as far into the 3m canal if you draw a picture of the situation, and the 5sqrt(2) gondola can continue onwards from this point on. Thank you for your reply. If I understand it correctly, gondola turned 45 degrees and touches sides of the canal at both ends and touches the 'inner' edge of the turning with its side. That is the diagonal of the (2+3)*(2+3) square. Yes, it can go on, but I don't think it could go back, unless it bends. To imagine, I propose to make the difference of widths greater, like 1 before turn and 100 after. | ||
hypercube
Hungary2735 Posts
On June 17 2017 05:36 Acrofales wrote: I thought I had a simple solution, but it breaks if any list in your subdivisions has length equal to a power of 2 (that adds 1, which can occur at different points in the tree). So doesn't work, and given the weirdness of your algorithm, I'm not sure there's an easy way of figuring out how often you'll run into a power of 2. I think I have an idea. Let's write the sets in rows like travis did, so the k-th row will have 2^(k-1) sets. So if we need K rows, we will have 2^K - 1 sets in total. Unfortunately, this only works if we terminate in a perfect row (e.g. a combination of 3s and 2s, that can't be broken down with our rule). So here's an outline: 0. Observe that there is at most two unique (and consecutive) elements in any given row. 1. Prove that there is at most 1 non-perfect row. That is a row which has both elements of n > 1 and n <= 1. I will refer to this as the final row. 2. Give a formula for the sum of elements in a row. This is doable because exactly one of n and n-1 so the sum of the child elements is one less than the parent element. 3. Use this formula to calculate the number of rows, up to and including the first non-perfect row. (call this K) 4. Use the same formula to calculate the number of ineligible elements in the final row. (call this D) Using the original idea, the final answer is 2^K - D - 1. edit: 3 seems the trickiest, I'm pretty sure I can do the others. | ||
CecilSunkure
United States2829 Posts
On June 09 2017 04:13 CecilSunkure wrote: I've been eager to learn about Fourier transform. In particular I wanted to use it to do pitch adjustments of sound samples. I have some code here for playing sounds, and want to add some pitch adjustment stuff. Would anyone mind chatting with me about the mathematics? I was hoping to find someone knowledge about Fourier transforms and their applications that I could bounce a bunch of questions off of. Please PM me if anyone would be so kind! Well it took a while, but after some studying I ended up getting down an implementation. I referenced "Computational Frameworks for the Fast Fourier Transform" by Charles Van Loan. I also found two good reference implementations here and here. The first link is an implementation of some algorithms from the Van Loan book, which helped show a proper way to convert algorithms to C and verify for correctness. The second link by Paul Bourke is probably the most popular FFT implementation in existence. The Bourke implementation has a sort of nasty side-effect of scaling floating point error across the DFT, so for large inputs the results can zero out early. This can easily be fixed by adding in some direct cos/sin calls, so I did that. In the end I got down my own implementation after referencing all 3 pieces mentioned above. Luckily all the Van Loan book is in vector and matrix algebra, something I'm already good at. Anyways, here's my current implementation. I'll probably work on it a little more to create a more useful API. Also the final scale loop in the if statement ( sign < 0 ) would be a good candidate for SIMD ops. My implementation is in a more modern style than the older ones, so it should be a little faster due to less branch misses in favor of a little more raw computation. Also there's a symmetry to cut computational cost in half that I've yet to implement. But this is fine for now: + Show Spoiler + #include <math.h> | ||
Deleted User 3420
24492 Posts
| ||
Simberto
Germany11032 Posts
On June 17 2017 06:00 Amanebak wrote: Show nested quote + On June 17 2017 05:42 Simberto wrote: On June 17 2017 04:53 Amanebak wrote: Hey. I stumbled across a problem like this: What is the longest gondola that can take a right-angle turn of a Venetian canal? The width of the canal is 2, respectively 3 length units before, resp. after the turn. I apologize for my English. Unless i missed something, the result is 5*sqrt(2). The gondola needs to be able fit into the diagonal of the (2+3)*(2+3) square, which has a length of 5 sqrt (2) At that point, 2sqrt(2) of the gondola is in the thinner canal, and 3sqrt(2) is in the thicker canal. It is obvious that no longer gondola could reach as far into the 3m canal if you draw a picture of the situation, and the 5sqrt(2) gondola can continue onwards from this point on. Thank you for your reply. If I understand it correctly, gondola turned 45 degrees and touches sides of the canal at both ends and touches the 'inner' edge of the turning with its side. That is the diagonal of the (2+3)*(2+3) square. Yes, it can go on, but I don't think it could go back, unless it bends. To imagine, I propose to make the difference of widths greater, like 1 before turn and 100 after. Hm, i calculated it another way, and got a better result: Just take a look at any rectangle which touch the corner of the canal. Before (and after) the turn, they all have the lengths (2+x) and (3+y), where 2/y = x/3 (intercept theorem). Thus, we are looking at the diagonal of a rectangle with sides (2+x) and (3+6/x), and especially for the minimum of those diagonals. The diagonal has the length of f(x) = Sqrt((2+x)²+(3+6/x)²) and thus the derivative of: f'(x) = 1/2f(x) * (2*(2+x)- (12/x²)*(3+6/x) Which you would now need to find the zeroes of. (I had mathematica do it because i am lazy, the zero is apparently at (18)^(1/3). (And further checks will almost certainly prove it to be a minimum That means that the lowest possible length of the gondola is f( (18)^(1/3)), which you can simplify to Sqrt (13 + 6*18^(1/3) + 3* 18^(2/3)), which is about 7.02, and indeed slightly less than 5Sqrt(2). Sorry for that. | ||
Deleted User 3420
24492 Posts
| ||
BrTarolg
United Kingdom3574 Posts
I *still* have no idea what's going on most of the time, inc in this thread lmao | ||
Amanebak
Czech Republic528 Posts
On June 17 2017 07:05 Simberto wrote: Show nested quote + On June 17 2017 06:00 Amanebak wrote: On June 17 2017 05:42 Simberto wrote: On June 17 2017 04:53 Amanebak wrote: Hey. I stumbled across a problem like this: What is the longest gondola that can take a right-angle turn of a Venetian canal? The width of the canal is 2, respectively 3 length units before, resp. after the turn. I apologize for my English. Unless i missed something, the result is 5*sqrt(2). The gondola needs to be able fit into the diagonal of the (2+3)*(2+3) square, which has a length of 5 sqrt (2) At that point, 2sqrt(2) of the gondola is in the thinner canal, and 3sqrt(2) is in the thicker canal. It is obvious that no longer gondola could reach as far into the 3m canal if you draw a picture of the situation, and the 5sqrt(2) gondola can continue onwards from this point on. Thank you for your reply. If I understand it correctly, gondola turned 45 degrees and touches sides of the canal at both ends and touches the 'inner' edge of the turning with its side. That is the diagonal of the (2+3)*(2+3) square. Yes, it can go on, but I don't think it could go back, unless it bends. To imagine, I propose to make the difference of widths greater, like 1 before turn and 100 after. Hm, i calculated it another way, and got a better result: Just take a look at any rectangle which touch the corner of the canal. Before (and after) the turn, they all have the lengths (2+x) and (3+y), where 2/y = x/3 (intercept theorem). Thus, we are looking at the diagonal of a rectangle with sides (2+x) and (3+6/x), and especially for the minimum of those diagonals. The diagonal has the length of f(x) = Sqrt((2+x)²+(3+6/x)²) and thus the derivative of: f'(x) = 1/2f(x) * (2*(2+x)- (12/x²)*(3+6/x) Which you would now need to find the zeroes of. (I had mathematica do it because i am lazy, the zero is apparently at (18)^(1/3). (And further checks will almost certainly prove it to be a minimum That means that the lowest possible length of the gondola is f( (18)^(1/3)), which you can simplify to Sqrt (13 + 6*18^(1/3) + 3* 18^(2/3)), which is about 7.02, and indeed slightly less than 5Sqrt(2). Sorry for that. Good job! There is another way, instead of using intercept theorem. You consider diagonals that touch the edge with their sides and finds the minimal one, using \alpha -- angle between the latter direction of the canal and the diagonal. We want to minimize function l = l_1+l_2 = 3/sin(\alpha) +2/cos(\alpha) I got something like \alpha_min = \arctan \sqrt[3](3/2), which is interesting to me. If we generalize this a bit, we take a, resp. b as parameters, instead of 2, resp. 3 and think of symmetries of this problem, we conclude \alpha_min (a,b)=\pi/2-\alpha_min (b,a), which demonstrates that \arctan(x)+\argtan (1/x) = \pi/2, if I am not mistaken. | ||
Kadungon
41 Posts
On June 12 2017 02:45 CecilSunkure wrote: So I've spent a day studying Fourier Transform. So far the math is very understandable, at least on how to apply it. Understanding why it works and specifically what it does is more challenging. Most resources on the subject are just absolutely awful, and I may have to go out and buy and old text book to get good information. It seems like FFT implementations popped up around the 80s-90s, and nobody ever really looked at them again in depth. Since then everyone takes and old implementation and wraps it. Well there's FFTW, but that library is a software engineering nightmare. It's a horribly obfuscated and heavyweight solution for a particularly small function. But what can you expect from a bunch of academics. You need to tread FFTW3 as a black box, because that is what it is supposed to be. It is used by Matlab and free to use for academics. So it is an industry standard. The real challenge is to be able to derive all the math and understand it in all its correctness. Only this way can I write a good implementation. Well, this is just not true. You implement it as a black box. There is no point understanding what is inside, as you are just implementing it. If you want to improve it or change it, then you need to know what is inside the box. BTW, when I did some FFTW stuff and I wanted to test correctness, I got into difficulties because defining PI with 12 decimals, or even 30, wasn't accurate enough, and rounding would cause funky stuff, resulting in frequency bins that weren't supposed to fill up, to be filled, because of oscillations in how each sin or cos call was rounded each period. On June 17 2017 10:29 BrTarolg wrote: Man, i have a degree in maths with a focus on pure I *still* have no idea what's going on most of the time, inc in this thread lmao That experience I get all over again anew every 3 or 4 weeks. You talk to people or read some reference, and suddenly there exists a whole new field, with all it's own intricacies, that you never knew about, barely understand, and that you think you want to know more about. But that is just impossible. So you figure out some silly pragmatic workaround, accepting that you are just one person with finite time and finite talent. | ||
CecilSunkure
United States2829 Posts
On June 17 2017 20:28 Kadungon wrote: Well, this is just not true. You implement it as a black box. There is no point understanding what is inside, as you are just implementing it. If you want to improve it or change it, then you need to know what is inside the box. But that's what I did. Improve and change it. Obviously not mathematically improve or change, just in terms of software engineering benefits. | ||
Deleted User 3420
24492 Posts
i want to write a sum: from i=1 to n of: 1/2*(i-1)i But I don't actually want i to stop when i = n. I want i to stop when the sum of "i values" has reached n. How do I do that? It's like if I could write my sum as "from i = i +1 to n" Example: If n = 10 I want my sum to go through i values of: 1, 2, 3, 4 - then STOP. Which gives me a sum of 0+1+3+6 = 10 Is the only way to do this to solve for the relationship between what I want i to do, and n? Because I am not sure what the relationship is. | ||
esla_sol
United States756 Posts
You and I are playing a game. We each shout out a number 1-100 every 5 seconds. Once someone says a number, that person can't say it again. What's the probability we match at least once? | ||
HKTPZ
105 Posts
f(x) being the sum of (-i+i^2)/2, from i to x Is that what you are looking for? @travis | ||
Deleted User 3420
24492 Posts
can I ask how you got it? | ||
| ||
StarCraft 2 StarCraft: Brood War Dota 2 Counter-Strike Super Smash Bros Heroes of the Storm Other Games summit1g4291 Grubby2803 B2W.Neo939 Hui .602 FrodaN208 NuckleDu132 KnowMe118 Trikslyr105 Mew2King47 EmSc Tv 19 Organizations Other Games StarCraft 2 StarCraft: Brood War StarCraft 2 StarCraft: Brood War
StarCraft 2 • Hupsaiya 18 StarCraft: Brood War• Kozan • Poblha • Migwel • Laughngamez YouTube • aXEnki • LaughNgamez Trovo • IndyKCrew • intothetv • Gussbus Dota 2 League of Legends Other Games |
Korean StarCraft League
Afreeca Starleague
hero vs Soulkey
AfreecaTV Pro Series
Reynor vs Cure
ESL Pro Tour
World Team League
ESL Pro Tour
BSL
Zhanhun vs DragOn
Dewalt vs Sziky
CSO Cup
Replay Cast
Sparkling Tuna Cup
[ Show More ] ESL Pro Tour
World Team League
ESL Pro Tour
BSL
Gypsy vs Bonyth
Mihu vs XiaoShuai
ESL Open Cup
ESL Open Cup
ESL Open Cup
ESL Pro Tour
ESL Pro Tour
ESL Pro Tour
ESL Pro Tour
|
|