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
France155 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  
travis
United States22719 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
Spain11704 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
Germany6294 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 = 2n1 total sets in this algorithm. An exact number is going to be harder to get.  
Liebig
France155 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  
travis
United States22719 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 Republic454 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 rightangle 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
Hungary2731 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 kth row will have 2^(k1) 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 nonperfect 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 n1 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 nonperfect 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 States2816 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 sideeffect 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>  
travis
United States22719 Posts
 
Simberto
Germany6294 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 rightangle 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.  
travis
United States22719 Posts
 
BrTarolg
United Kingdom3380 Posts
I *still* have no idea what's going on most of the time, inc in this thread lmao  
Amanebak
Czech Republic454 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 rightangle 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 80s90s, 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 States2816 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.  
travis
United States22719 Posts
i want to write a sum: from i=1 to n of: 1/2*(i1)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 States742 Posts
You and I are playing a game. We each shout out a number 1100 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
78 Posts
f(x) being the sum of (i+i^2)/2, from i to x Is that what you are looking for? @travis  
travis
United States22719 Posts
can I ask how you got it?  
 

Next event in 1h 54m
[ Submit Event ] 
StarCraft 2 StarCraft: Brood War Jaedong 7813 Other GamesBeSt 437 Last 333 Reach 298 Livibee 267 Light 224 Horang2 147 Dragon 122 Killer 64 Shine 38 [ Show more ] Organizations
StarCraft 2 • KofyeinTV 12 StarCraft: Brood War• D4rkn0ob1k 5 • samosel 3 • IXLRunaMok 3 • nightgamer69 2 • TheGrinder 2 • Gladiusreal1 1 • Axeltl 1 • Freeedom 1 CounterStrike: Global Offensive Other Games • itmeJP3520
• MrLlama715 • BlizzardZHTW 652 • LoL JCG90 • SwInD42071 • KoiKarpfenTomahawk 20 • Youkai_WoT20 • QuickStriker13 • cheeseheadlogic6 • Floppy_Flams5 • Puraaj4 • DJay_2 • Kumihothesilent1 • Midday1 • Funkmastermp0 
ESL One
G2 Esports vs Team EnVyUs
Gambit Esports vs BIG
Ariel Cup
Master's Coliseum
GuMiho vs ByuN
Dark vs INnoVation
soO vs Rogue
Go4SC2
OSC
Kings of the North
Great British Starleague
Clash for Char
ESL One
Cloud9 vs compLexity Gaming
TBD vs CLG
The Gauntlet
[ Show More ] Colonial Wars
OSC
StarCraft II StarLeague
ByuL vs aLive
Classic vs herO
Maru vs Stats
Dear vs Dark
Solar vs INnoVation
OSC
OSC
Corsair Cup
Fantasy Expo Challenge
Proxy Tempest
Gosu_PvP Cup
Ballistix Brawl
OlimoLeague
ESL ESEA Pro League
HellRaisers vs Heroic
G2 Esports vs FaZe
mousesports vs GODSENT
BIG vs Fnatic
Great British Starleague
ESL ESEA Pro League
OpTiC Gaming vs Bee's Money Crew
SK Gaming vs Team Liquid
Splyce vs NRG eSports
CLG vs Cloud9
WCS Regional Challengers
GSL Code S
soO vs Dark
Classic vs Rogue
Proxy Tempest
Great British Starleague
Gosu_PvP Cup
WCS Regional Challengers
StarCraft II StarLeague
Bunny vs Impact
jjakji vs ByuN
soO vs Rogue
Gosu_PvP Cup
Go4SC2
Proxy Tempest
Gosu_PvP Cup
Great British Starleague
WCS Regional Challengers
Showmatch
GSL Code S
Stats vs Hurricane
TY vs Patience
ESL SC Remastered Cup
StarCraft II StarLeague
STK
WCS Regional Challengers

