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 States22865 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
Spain12240 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
Germany6726 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 States22865 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 Republic462 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
Hungary2732 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 States2828 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 States22865 Posts
 
Simberto
Germany6726 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 States22865 Posts
 
BrTarolg
United Kingdom3514 Posts
I *still* have no idea what's going on most of the time, inc in this thread lmao  
Amanebak
Czech Republic462 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 States2828 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 States22865 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 States744 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
83 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 States22865 Posts
can I ask how you got it?  
 

Next event in 55m
[ Submit Event ] 
StarCraft 2 ViBE 595 StarCraft: Brood WarROOTSuperNova 270 UpATree 239 oGsTOP 155 JinAirCreator 95 Leenock 59 Ragnarok 28 Zanster 28 BEARDiaguz 3 CounterStrike: Global Offensive Other Games Organizations CounterStrike: Global Offensive StarCraft 2 StarCraft: Brood War
StarCraft 2 StarCraft: Brood War CounterStrike: Global Offensive Other Games • TSM TheOddOne1327
• HappyZerGling950 • LevelUpLive429 • Fitzyhere187 • :PC:Spacegoon43 • PengWin_SC20 • Sheezle16 • SCMothership3 
DreamHack Masters
FaZe vs Team EnVyUs
mousesports vs SK Gaming
Fnatic vs Renegades
Team Liquid vs Gambit Esports
Heroes Major League
OSC
Heroes Major League
Heroes of Ananas
WardiTV Weekly
Esports Championship Se…
G2 Esports vs Fnatic
G2 Esports vs Ninjas in Pyjamas
Shinhan Tank Proleague
Heroes Major League
OSC
[ Show More ] GSL Code S
Scarlett vs Patience
Losira vs GuMiho
OSC
DreamHack Masters
Heroes Major League
OSC
WCS Regional Challengers
Serral vs Starbuck
PtitDrogo vs Bly
REGENERATE OPEN WEEKLY…
BSL
Heroes Major League
WCS Regional Challengers
MaSa vs Starkiller
PandaBearMe vs Cicada
Heroes Major League
Platypro Weekly
Copa América
SpeCial vs TheZergLord
HalfBreed vs Erik
OSC
WCS Regional Challengers
NationWars V
Mexico vs Netherlands
South Korea vs Finland
DreamHack Masters
Afreeca Starleague
Shuttle vs Rain
Go4SC2
Have At You
Copa América
Kelazhur vs DarkUnnamed
Dark vs LsEbA
OSC
OSC
Shinhan Tank Proleague
OSC
Heroes Major League
Afreeca Starleague
hero vs Mind
OlimoLeague
ESL ESEA Pro League
Team EnVyUs vs Heroic
mousesports vs Space Soldiers
AGO Gaming vs Fnatic
WardiTV Weekly
Esports Championship Se…
Astralis vs G2 Esports
FaZe vs G2 Esports
ESL ESEA Pro League
Rogue vs Renegades
OpTiC Gaming vs Team Dignitas
Ghost Gaming vs Luminosity Gaming
Ballistix Brawl
Heroes Major League
GSL Code S
sOs vs TRUE
KeeN vs Solar
ESL ESEA Pro League
Astralis vs Team EnVyUs
Natus Vincere vs Fnatic
HellRaisers vs Team LDLC.com
Esports Championship Se…
G2 Esports vs Gambit Esports
mousesports vs Gambit Esports
Proxy Tempest
Shinhan Tank Proleague
ESL ESEA Pro League
Team Liquid vs compLexity Gaming
Renegades vs Team Dignitas
Rogue vs Cloud9
ESL ESEA Pro League
Ninjas in Pyjamas vs Astralis
Heroic vs AGO Gaming
Team LDLC.com vs Fnatic
Natus Vincere vs G2 Esports
FaZe vs Space Soldiers
mousesports vs Team EnVyUs
HellRaisers vs North
Go4SC2
WardiTV Weekly
Esports Championship Se…
Virtus.pro vs GODSENT
ESL ESEA Pro League
Team Liquid vs OpTiC Gaming
Splyce vs Cloud9
Ghost Gaming vs compLexity Gaming
Luminosity Gaming vs NRG eSports
SK Gaming vs Renegades
Rogue vs Team Dignitas

