Search Results

Search found 19 results on 1 pages for 'bisect'.

Page 1/1 | 1 

  • Java's equivalent to bisect in python

    - by systemsfault
    Hello all, Is there a java equivalent to python's bisect library? With python's bisect you can do array bisection with directions. For instance bisect.bisect_left does: Locate the proper insertion point for item in list to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used.

    Read the article

  • How does mercurial's bisect work when the range includes branching?

    - by Joshua Goldberg
    If the bisect range includes multiple branches, how does hg bisect's search work. Does it effectively bisect each sub-branch (I would think that would be inefficient)? For instance, borrowing, with gratitude, a diagram from an answer to this related question, what if the bisect got to changeset 7 on the "good" right-side branch first. @ 12:8ae1fff407c8:bad6 | o 11:27edd4ba0a78:bad5 | o 10:312ba3d6eb29:bad4 |\ | o 9:68ae20ea0c02:good33 | | | o 8:916e977fa594:good32 | | | o 7:b9d00094223f:good31 | | o | 6:a7cab1800465:bad3 | | o | 5:a84e45045a29:bad2 | | o | 4:d0a381a67072:bad1 | | o | 3:54349a6276cc:good4 |/ o 2:4588e394e325:good3 | o 1:de79725cb39a:good2 | o 0:2641cc78ce7a:good1 Will it then look only between 7 and 12, missing the real first-bad that we care about? (thus using "dumb" numerical order) or is it smart enough to use the full topography and to know that the first bad could be below 7 on the right-side branch, or could still be anywhere on the left-side branch. The purpose of my question is both (a) just to understand the algorithm better, and (b) to understand whether I can liberally extend my initial bisect range without thinking hard about what branch I go to. I've been in high-branching bisect situations where it kept asking me after every test to extend beyond the next merge, so that the whole procedure was essentially O(n). I'm wondering if I can just throw the first "good" marker way back past some nest of merges without thinking about it much, and whether that would save time and give correct results.

    Read the article

  • Is there a recommended command for "hg bisect --command"?

    - by blokeley
    I have an emergent bug that I've got to track down tomorrow. I know a previous hg revision which was good so I'm thinking about using hg bisect. However, I'm on Windows and don't want to get into DOS scripting. Ideally, I'd be able to write a Python unit test and have hg bisect use that. This is my first attempt. bisector.py #!/usr/bin/env python import sys import unittest class TestCase(unittest.TestCase): def test(self): #raise Exception('Exception for testing.') #self.fail("Failure for testing.") pass def main(): suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestCase) result = unittest.TestResult() suite.run(result) if result.errors: # Skip the revision return 125 if result.wasSuccessful(): return 0 else: return 1 if '__main__' == __name__: sys.exit(main()) Perhaps I could then run: hg bisect --reset hg bisect --bad hg bisect --good -r 1 hg bisect --command=bisector.py Is there a better way of doing it? Thanks for any advice.

    Read the article

  • Gerrit, git and reviewing whole branch

    - by liori
    I'm now learning Gerrit (which is the first code review tool I use). Gerrit requires a reviewed change to consist of a single commit. My feature branch has about 10 commits. The gerrit-prefered way is to squash those 10 commits into a single one. However this way if the commit will be merged into the target branch, the internal history of that feature branch will be lost. For example, I won't be able to use git-bisect to bisect into those commits. Am I right? I am a little bit worried about this state of things. What is the rationale for this choice? Is there any way of doing this in Gerrit without losing history?

    Read the article

  • How to setup and teardown temporary django db for unit testing?

    - by blokeley
    I would like to have a python module containing some unit tests that I can pass to hg bisect --command. The unit tests are testing some functionality of a django app, but I don't think I can use hg bisect --command manage.py test mytestapp because mytestapp would have to be enabled in settings.py, and the edits to settings.py would be clobbered when hg bisect updates the working directory. Therefore, I would like to know if something like the following is the best way to go: import functools, os, sys, unittest sys.path.append(path_to_myproject) os.environ['DJANGO_SETTINGS_MODULE'] = 'myapp.settings' def with_test_db(func): """Decorator to setup and teardown test db.""" @functools.wraps def wrapper(*args, **kwargs): try: # Set up temporary django db func(*args, **kwargs) finally: # Tear down temporary django db class TestCase(unittest.TestCase): @with_test_db def test(self): # Do some tests using the temporary django db self.fail('Mark this revision as bad.') if '__main__' == __name__: unittest.main() I should be most grateful if you could advise either: If there is a simpler way, perhaps subclassing django.test.TestCase but not editing settings.py or, if not; What the lines above that say "Set up temporary django db" and "Tear down temporary django db" should be?

    Read the article

  • Segmentation fault in my C program

    - by user233542
    I don't understand why this would give me a seg fault. Any ideas? This is the function that returns the signal to stop the program (plus the other function that is called within this): double bisect(double A0,double A1,double Sol[N],double tol,double c) { double Amid,shot; while (A1-A0 > tol) { Amid = 0.5*(A0+A1); shot = shoot(Sol, Amid, c); if (shot==2.*Pi) { return Amid; } if (shot > 2.*Pi){ A1 = Amid; } else if (shot < 2.*Pi){ A0 = Amid; } } return 0.5*(A1+A0); } double shoot(double Sol[N],double A,double c) { int i,j; /*Initial Conditions*/ for (i=0;i<buff;i++) { Sol[i] = 0.; } for (i=buff+l;i<N;i++) { Sol[i] = 2.*Pi; } Sol[buff]= 0; Sol[buff+1]= A*exp(sqrt(1+3*c)*dx); for (i=buff+2;i<buff+l;i++) { Sol[i] = (dx*dx)*( sin(Sol[i-1]) + c*sin(3.*(Sol[i-1])) ) - Sol[i-2] + 2.*Sol[i-1]; } return Sol[i-1]; } The values buff, l, N are defined using a #define statement. l = 401, buff = 50, N = 2000 Here is the full code: #include <stdio.h> #include <stdlib.h> #include <math.h> #define w 10 /*characteristic width of a soliton*/ #define dx 0.05 /*distance between lattice sites*/ #define s (2*w)/dx /*size of soliton shape*/ #define l (int)(s+1) /*array length for soliton*/ #define N (int)2000 /*length of field array--lattice sites*/ #define Pi (double)4*atan(1) #define buff (int)50 double shoot(double Sol[N],double A,double c); double bisect(double A0,double A1,double Sol[N],double tol,double c); void super_pos(double antiSol[N],double Sol[N],double phi[][N]); void vel_ver(double phi[][N],double v,double c,int tsteps,double dt); int main(int argc, char **argv) { double c,Sol[N],antiSol[N],A,A0,A1,tol,v,dt; int tsteps,i; FILE *fp1,*fp2,*fp3; fp1 = fopen("soliton.dat","w"); fp2 = fopen("final-phi.dat","w"); fp3 = fopen("energy.dat","w"); printf("Please input the number of time steps:"); scanf("%d",&tsteps); printf("Also, enter the time step size:"); scanf("%lf",&dt); do{ printf("Please input the parameter c in the interval [-1/3,1]:"); scanf("%lf",&c);} while(c < (-1./3.) || c > 1.); printf("Please input the inital speed of eiter soliton:"); scanf("%lf",&v); double phi[tsteps+1][N]; tol = 0.0000001; A0 = 0.; A1 = 2.*Pi; A = bisect(A0,A1,Sol,tol,c); shoot(Sol,A,c); for (i=0;i<N;i++) { fprintf(fp1,"%d\t",i); fprintf(fp1,"%lf\n",Sol[i]); } fclose(fp1); super_pos(antiSol,Sol,phi); /*vel_ver(phi,v,c,tsteps,dt); for (i=0;i<N;i++){ fprintf(fp2,"%d\t",i); fprintf(fp2,"%lf\n",phi[tsteps][i]); }*/ } double shoot(double Sol[N],double A,double c) { int i,j; /*Initial Conditions*/ for (i=0;i<buff;i++) { Sol[i] = 0.; } for (i=buff+l;i<N;i++) { Sol[i] = 2.*Pi; } Sol[buff]= 0; Sol[buff+1]= A*exp(sqrt(1+3*c)*dx); for (i=buff+2;i<buff+l;i++) { Sol[i] = (dx*dx)*( sin(Sol[i-1]) + c*sin(3.*(Sol[i-1])) ) - Sol[i-2] + 2.*Sol[i-1]; } return Sol[i-1]; } double bisect(double A0,double A1,double Sol[N],double tol,double c) { double Amid,shot; while (A1-A0 > tol) { Amid = 0.5*(A0+A1); shot = shoot(Sol, Amid, c); if (shot==2.*Pi) { return Amid; } if (shot > 2.*Pi){ A1 = Amid; } else if (shot < 2.*Pi){ A0 = Amid; } } return 0.5*(A1+A0); } void super_pos(double antiSol[N],double Sol[N],double phi[][N]) { int i; /*for (i=0;i<N;i++) { phi[i]=0; } for (i=buffer+s;i<1950-s;i++) { phi[i]=2*Pi; }*/ for (i=0;i<N;i++) { antiSol[i] = Sol[N-i]; } /*for (i=0;i<s+1;i++) { phi[buffer+j] = Sol[j]; phi[1549+j] = antiSol[j]; }*/ for (i=0;i<N;i++) { phi[0][i] = antiSol[i] + Sol[i] - 2.*Pi; } } /* This funciton will set the 2nd input array to the derivative at the time t, for all points x in the lattice */ void deriv2(double phi[][N],double DphiDx2[][N],int t) { //double SolDer2[s+1]; int x; for (x=0;x<N;x++) { DphiDx2[t][x] = (phi[buff+x+1][t] + phi[buff+x-1][t] - 2.*phi[x][t])/(dx*dx); } /*for (i=0;i<N;i++) { ptr[i] = &SolDer2[i]; }*/ //return DphiDx2[x]; } void vel_ver(double phi[][N],double v,double c,int tsteps,double dt) { int t,x; double d1,d2,dp,DphiDx1[tsteps+1][N],DphiDx2[tsteps+1][N],dpdt[tsteps+1][N],p[tsteps+1][N]; for (t=0;t<tsteps;t++){ if (t==0){ for (x=0;x<N;x++){//inital conditions deriv2(phi,DphiDx2,t); dpdt[t][x] = DphiDx2[t][x] - sin(phi[t][x]) - sin(3.*phi[t][x]); DphiDx1[t][x] = (phi[t][x+1] - phi[t][x])/dx; p[t][x] = -v*DphiDx1[t][x]; } } for (x=0;x<N;x++){//velocity-verlet phi[t+1][x] = phi[t][x] + dt*p[t][x] + (dt*dt/2)*dpdt[t][x]; p[t+1][x] = p[t][x] + (dt/2)*dpdt[t][x]; deriv2(phi,DphiDx2,t+1); dpdt[t][x] = DphiDx2[t][x] - sin(phi[t+1][x]) - sin(3.*phi[t+1][x]); p[t+1][x] += (dt/2)*dpdt[t+1][x]; } } } So, this really isn't due to my overwriting the end of the Sol array. I've commented out both functions that I suspected of causing the problem (bisect or shoot) and inserted a print function. Two things happen. When I have code like below: double A,Pi,B,c; c=0; Pi = 4.*atan(1.); A = Pi; B = 1./4.; printf("%lf",B); B = shoot(Sol,A,c); printf("%lf",B); I get a segfault from the function, shoot. However, if I take away the shoot function so that I have: double A,Pi,B,c; c=0; Pi = 4.*atan(1.); A = Pi; B = 1./4.; printf("%lf",B); it gives me a segfault at the printf... Why!?

    Read the article

  • Less graphics power all the sudden (Intel HD 3000)

    - by queueoverflow
    I have a Intel Sandy Bridge i5 with the HD 3000 graphics card. I used to be able to play Urban Terror and Nexuiz comfortably with 85 and 60 frames per seconds until mid/end of October 2012, the former even on a full HD display with that many frames. Now I have around 30 to 45 on the smaller laptop screen and around 20 to 30 on the external monitor. Did something happen to Kubuntu 12.04 so that it has less graphics performance than previously? Update I looked into the system monitor and could not detect anything being at the maximum. The four CPU cores were pretty much bored, the 8 GB RAM were filled with maybe 2 GB. And I ran intel_cpu_top and did not notice anything at its limit. See the output. after Kernel bisecting I now did a kernel bisect and tried 3.2.0-23, 3.2.0-27, 3.2.0-29 and 3.2.0-30 and all had full graphics power. Interestingly, I then had full power when I just booted back into the regular 3.2.0-32 kernel. This does not make sense to me …

    Read the article

  • Any tool to make git build every commit to a branch in a seperate repository?

    - by Wayne
    A git tool that meets the specs below is needed. Does one already exists? If not, I will create a script and make it available on GitHub for others to use or contribute. Is there a completely different and better way to solve the need to build/test every commit to a branch in a git repository? Not just to the latest but each one back to a certain staring point. Background: Our development environment uses a separate continuous integration server which is wonderful. However, it is still necessary to do full builds locally on each developer's PC to make sure the commit won't "break the build" when pushed to the CI server. Unfortunately, with auto unit tests, those build force the developer to wait 10 or 15 minutes for a build every time. To solve this we have setup a "mirror" git repository on each developer PC. So we develop in the main repository but anytime a local full build is needed. We run a couple commands in a in the mirror repository to fetch, checkout the commit we want to build, and build. It's works extremely lovely so we can continue working in the main one with the build going in parallel. There's only one main concern now. We want to make sure every single commit builds and tests fine. But we often get busy and neglect to build several fresh commits. Then if it the build fails you have to do a bisect or manually figure build each interim commit to figure out which one broke. Requirements for this tool. The tool will look at another repo, origin by default, fetch and compare all commits that are in branches to 2 lists of commits. One list must hold successfully built commits and the other lists commits that failed. It identifies any commit or commits not yet in either list and begins to build them in a loop in the order that they were committed. It stops on the first one that fails. The tool appropriately adds each commit to either the successful or failed list after it as attempted to build each one. The tool will ignore any "legacy" commits which are prior to the oldest commit in the success list. This logic makes the starting point possible in the next point. Starting Point. The tool building a specific commit so that, if successful it gets added to the success list. If it is the earliest commit in the success list, it becomes the "starting point" so that none of the commits prior to that are examined for builds. Only linear tree support? Much like bisect, this tool works best on a commit tree which is, at least from it's starting point, linear without any merges. That is, it should be a tree which was built and updated entirely via rebase and fast forward commits. If it fails on one commit in a branch it will stop without building the rest that followed after that one. Instead if will just move on to another branch, if any. The tool must do these steps once by default but allow a parameter to loop with an option to set how many seconds between loops. Other tools like Hudson or CruiseControl could do more fancy scheduling options. The tool must have good defaults but allow optional control. Which repo? origin by default. Which branches? all of them by default. What tool? by default an executable file to be provided by the user named "buildtest", "buildtest.sh" "buildtest.cmd", or buildtest.exe" in the root folder of the repository. Loop delay? run once by default with option to loop after a number of seconds between iterations.

    Read the article

  • run windows command from bash with output to standard out?

    - by Wayne
    Folks, I'm using git tools such as git bisect run which need to call a command to build and test my project. My command to do is nant which is a windows program. Or a build.cmd script which calls nant. It's easy to get the bash to call the nant build to run. But the hard part is how to get the standard output written to a file? I even installed the Windows PowerShell to try running a command from bash. Again, it works but the standard output fill says "permission denied" when I try to read it while the build is going on.

    Read the article

  • Why is this the output of this python program?

    - by Andrew Moffat
    Someone from #python suggested that it's searching for module "herpaderp" and finding all the ones listed as its searching. If this is the case, why doesn't it list every module on my system before raising ImportError? Can someone shed some light on what's happening here? import sys class TempLoader(object): def __init__(self, path_entry): if path_entry == 'test': return raise ImportError def find_module(self, fullname, path=None): print fullname, path return None sys.path.insert(0, 'test') sys.path_hooks.append(TempLoader) import herpaderp output: 16:00:55 $> python wtf.py herpaderp None apport None subprocess None traceback None pickle None struct None re None sre_compile None sre_parse None sre_constants None org None tempfile None random None __future__ None urllib None string None socket None _ssl None urlparse None collections None keyword None ssl None textwrap None base64 None fnmatch None glob None atexit None xml None _xmlplus None copy None org None pyexpat None problem_report None gzip None email None quopri None uu None unittest None ConfigParser None shutil None apt None apt_pkg None gettext None locale None functools None httplib None mimetools None rfc822 None urllib2 None hashlib None _hashlib None bisect None Traceback (most recent call last): File "wtf.py", line 14, in <module> import herpaderp ImportError: No module named herpaderp

    Read the article

  • Implement functionality in PHP?

    - by Rachel
    How can we Implement Bisect Python functionality in PHP Implement function bisect_left($arr, $item); as a pure-PHP routine to do a binary-bisection search for the position at which to insert $item into $list, maintaining the sort order therein. Assumptions: Assume that $arr is already sorted by whatever comparisons would be yielded by the stock PHP < operator, and that it's indexed on ints. The function should return an int, representing the index within the array at which $item would be inserted to maintain the order of the array. The returned index should be below any elements in $arr equal to $item, i.e., the insertion index should be "to the left" of anything equal to $item. Search routine should not be linear! That is, it should honor the name, and should attempt to find it by iteratively bisecting the list and comparing only around the midpoint.

    Read the article

  • C lang. -- Error: Segmentaion fault

    - by user233542
    I don't understand why this would give me a seg fault. Any ideas? this is the function that returns the signal to stop the program: (below is the other function that is called within this) double bisect(double A0,double A1,double Sol[N],double tol,double c) { double Amid,shot; while (A1-A0 tol) { Amid = 0.5*(A0+A1); shot = shoot(Sol, Amid, c); if (shot==2.*Pi) { return Amid; } if (shot > 2.*Pi){ A1 = Amid; } else if (shot < 2.*Pi){ A0 = Amid; } } return 0.5*(A1+A0); } double shoot(double Sol[N],double A,double c) { int i,j; /Initial Conditions/ for (i=0;i for (i=buff+2;i return Sol[i-1]; } buff, l, N are defined using a #deine statement. l = 401, buff = 50, N = 2000 Thanks

    Read the article

  • A file was added to git on commit n. How do I add it instead to commit n-m?

    - by carleeto
    I have a branch. Half way through I noticed git was not tracking a file that it should have been and so I added it as part of a commit and continued with my work. Now, I'm doing a git bisect and all commits before the file was added do not build. So I'm thinking, I need to split the commit that added the file into two parts: the file add and the rest of the commit. I then need to re-order the commits so that the file add commit will be at the beginning of my branch. Is this the correct solution or is there a better way of doing it?

    Read the article

  • Which Firefox add-on is responsible for a rendering bug?

    - by Gilles
    I've found a page that isn't rendered correctly by Firefox with my usual profile. It is rendered correctly with a blank profile. I have quite a few add-ons. One of them is surely the culprit. How can I find out which? Userscripts often affect the rendering. But I turned off Greasemonkey, and it didn't help. So it's something else, presumably an extension (what else could it be? I have no chrome/userChrome.css.). I'm looking for an easy way to find out which one, easier than disabling a bunch of extensions and restarting umpteen times. Related: Create a tool to help users identify a problematic add-on by bisecting the list of installed add-ons — a similar problem which would admit a similar solution. I want to automate this as much as possible; something like git bisect, that doesn't require me to change my actual profile, would be ideal. A Linux-specific solution is fine with me.

    Read the article

  • git doesn't show where code was removed.

    - by Andrew Myers
    So I was tasked at replacing some dummy code that our project requires for historical compatibility reasons but has mysteriously dropped out sometime since the last release. Since disappearing code makes me nervous about what else might have gone missing but un-noticed I've been digging through the logs trying to find in what commit this handful of lines was removed. I've tried a number of things including "git log -S'add-visit-resource-pcf'", git blame, and even git bisect with a script that simply checks for the existence of the line but have been unable to pinpoint exactly where these lines were removed. I find this very perplexing, particularly since the last log entry (obtained by the above command) before my re-introduction of this code was someone else adding the code as well. commit 0b0556fa87ff80d0ffcc2b451cca1581289bbc3c Author: Andrew Date: Thu May 13 10:55:32 2010 -0400 Re-introduced add-visit-resource-pcf, see PR-65034. diff --git a/spike/hst/scheduler/defpackage.lisp b/spike/hst/scheduler/defpackage.lisp index f8e692d..a6f8d38 100644 --- a/spike/hst/scheduler/defpackage.lisp +++ b/spike/hst/scheduler/defpackage.lisp @@ -115,6 +115,7 @@ #:add-to-current-resource-pcf #:add-user-package-nickname #:add-value-criteria + #:add-visit-resource-pcf #:add-window-to-gs-params #:adjust-derived-resources #:adjust-links-candidate-criteria-types commit 9fb10e25572c537076284a248be1fbf757c1a6e1 Author: Bob Date: Sun Jan 17 18:35:16 2010 -0500 update-defpackage for Spike 33.1 Delivery diff --git a/spike/hst/scheduler/defpackage.lisp b/spike/hst/scheduler/defpackage.lisp index 983666d..47f1a9a 100644 --- a/spike/hst/scheduler/defpackage.lisp +++ b/spike/hst/scheduler/defpackage.lisp @@ -118,6 +118,7 @@ #:add-user-package-nickname #:add-value-criteria #:add-vars-from-proposal + #:add-visit-resource-pcf #:add-window-to-gs-params #:adjust-derived-resources #:adjust-links-candidate-criteria-types This is for one of our package definition files, but the relevant source file reflects something similar. Does anyone know what could be going on here and how I could find the information I want? It's not really that important but this kind of things makes me a bit nervous.

    Read the article

  • Return a list of imported Python modules used in a script?

    - by Jono Bacon
    Hi All, I am writing a program that categorizes a list of Python files by which modules they import. As such I need to scan the collection of .py files ad return a list of which modules they import. As an example, if one of the files I import has the following lines: import os import sys, gtk I would like it to return: ["os", "sys", "gtk"] I played with modulefinder and wrote: from modulefinder import ModuleFinder finder = ModuleFinder() finder.run_script('testscript.py') print 'Loaded modules:' for name, mod in finder.modules.iteritems(): print '%s ' % name, but this returns more than just the modules used in the script. As an example in a script which merely has: import os print os.getenv('USERNAME') The modules returned from the ModuleFinder script return: tokenize heapq __future__ copy_reg sre_compile _collections cStringIO _sre functools random cPickle __builtin__ subprocess cmd gc __main__ operator array select _heapq _threading_local abc _bisect posixpath _random os2emxpath tempfile errno pprint binascii token sre_constants re _abcoll collections ntpath threading opcode _struct _warnings math shlex fcntl genericpath stat string warnings UserDict inspect repr struct sys pwd imp getopt readline copy bdb types strop _functools keyword thread StringIO bisect pickle signal traceback difflib marshal linecache itertools dummy_thread posix doctest unittest time sre_parse os pdb dis ...whereas I just want it to return 'os', as that was the module used in the script. Can anyone help me achieve this?

    Read the article

  • Return a list of important Python modules in a script?

    - by Jono Bacon
    Hi All, I am writing a program that categorizes a list of Python files by which modules they import. As such I need to scan the collection of .py files ad return a list of which modules they import. As an example, if one of the files I import has the following lines: import os import sys, gtk I would like it to return: ["os", "sys", "gtk"] I played with modulefinder and wrote: from modulefinder import ModuleFinder finder = ModuleFinder() finder.run_script('testscript.py') print 'Loaded modules:' for name, mod in finder.modules.iteritems(): print '%s ' % name, but this returns more than just the modules used in the script. As an example in a script which merely has: import os print os.getenv('USERNAME') The modules returned from the ModuleFinder script return: tokenize heapq __future__ copy_reg sre_compile _collections cStringIO _sre functools random cPickle __builtin__ subprocess cmd gc __main__ operator array select _heapq _threading_local abc _bisect posixpath _random os2emxpath tempfile errno pprint binascii token sre_constants re _abcoll collections ntpath threading opcode _struct _warnings math shlex fcntl genericpath stat string warnings UserDict inspect repr struct sys pwd imp getopt readline copy bdb types strop _functools keyword thread StringIO bisect pickle signal traceback difflib marshal linecache itertools dummy_thread posix doctest unittest time sre_parse os pdb dis ...whereas I just want it to return 'os', as that was the module used in the script. Can anyone help me achieve this?

    Read the article

  • C lang. -- Error: Segmentation fault

    - by user233542
    I don't understand why this would give me a seg fault. Any ideas? This is the function that returns the signal to stop the program (plus the other function that is called within this): double bisect(double A0,double A1,double Sol[N],double tol,double c) { double Amid,shot; while (A1-A0 > tol) { Amid = 0.5*(A0+A1); shot = shoot(Sol, Amid, c); if (shot==2.*Pi) { return Amid; } if (shot > 2.*Pi){ A1 = Amid; } else if (shot < 2.*Pi){ A0 = Amid; } } return 0.5*(A1+A0); } double shoot(double Sol[N],double A,double c) { int i,j; /*Initial Conditions*/ for (i=0;i<buff;i++) { Sol[i] = 0.; } for (i=buff+l;i<N;i++) { Sol[i] = 2.*Pi; } Sol[buff]= 0; Sol[buff+1]= A*exp(sqrt(1+3*c)*dx); for (i=buff+2;i<buff+l;i++) { Sol[i] = (dx*dx)*( sin(Sol[i-1]) + c*sin(3.*(Sol[i-1])) ) - Sol[i-2] + 2.*Sol[i-1]; } return Sol[i-1]; } The values buff, l, N are defined using a #define statement. l = 401, buff = 50, N = 2000

    Read the article

  • A Taxonomy of Numerical Methods v1

    - by JoshReuben
    Numerical Analysis – When, What, (but not how) Once you understand the Math & know C++, Numerical Methods are basically blocks of iterative & conditional math code. I found the real trick was seeing the forest for the trees – knowing which method to use for which situation. Its pretty easy to get lost in the details – so I’ve tried to organize these methods in a way that I can quickly look this up. I’ve included links to detailed explanations and to C++ code examples. I’ve tried to classify Numerical methods in the following broad categories: Solving Systems of Linear Equations Solving Non-Linear Equations Iteratively Interpolation Curve Fitting Optimization Numerical Differentiation & Integration Solving ODEs Boundary Problems Solving EigenValue problems Enjoy – I did ! Solving Systems of Linear Equations Overview Solve sets of algebraic equations with x unknowns The set is commonly in matrix form Gauss-Jordan Elimination http://en.wikipedia.org/wiki/Gauss%E2%80%93Jordan_elimination C++: http://www.codekeep.net/snippets/623f1923-e03c-4636-8c92-c9dc7aa0d3c0.aspx Produces solution of the equations & the coefficient matrix Efficient, stable 2 steps: · Forward Elimination – matrix decomposition: reduce set to triangular form (0s below the diagonal) or row echelon form. If degenerate, then there is no solution · Backward Elimination –write the original matrix as the product of ints inverse matrix & its reduced row-echelon matrix à reduce set to row canonical form & use back-substitution to find the solution to the set Elementary ops for matrix decomposition: · Row multiplication · Row switching · Add multiples of rows to other rows Use pivoting to ensure rows are ordered for achieving triangular form LU Decomposition http://en.wikipedia.org/wiki/LU_decomposition C++: http://ganeshtiwaridotcomdotnp.blogspot.co.il/2009/12/c-c-code-lu-decomposition-for-solving.html Represent the matrix as a product of lower & upper triangular matrices A modified version of GJ Elimination Advantage – can easily apply forward & backward elimination to solve triangular matrices Techniques: · Doolittle Method – sets the L matrix diagonal to unity · Crout Method - sets the U matrix diagonal to unity Note: both the L & U matrices share the same unity diagonal & can be stored compactly in the same matrix Gauss-Seidel Iteration http://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method C++: http://www.nr.com/forum/showthread.php?t=722 Transform the linear set of equations into a single equation & then use numerical integration (as integration formulas have Sums, it is implemented iteratively). an optimization of Gauss-Jacobi: 1.5 times faster, requires 0.25 iterations to achieve the same tolerance Solving Non-Linear Equations Iteratively find roots of polynomials – there may be 0, 1 or n solutions for an n order polynomial use iterative techniques Iterative methods · used when there are no known analytical techniques · Requires set functions to be continuous & differentiable · Requires an initial seed value – choice is critical to convergence à conduct multiple runs with different starting points & then select best result · Systematic - iterate until diminishing returns, tolerance or max iteration conditions are met · bracketing techniques will always yield convergent solutions, non-bracketing methods may fail to converge Incremental method if a nonlinear function has opposite signs at 2 ends of a small interval x1 & x2, then there is likely to be a solution in their interval – solutions are detected by evaluating a function over interval steps, for a change in sign, adjusting the step size dynamically. Limitations – can miss closely spaced solutions in large intervals, cannot detect degenerate (coinciding) solutions, limited to functions that cross the x-axis, gives false positives for singularities Fixed point method http://en.wikipedia.org/wiki/Fixed-point_iteration C++: http://books.google.co.il/books?id=weYj75E_t6MC&pg=PA79&lpg=PA79&dq=fixed+point+method++c%2B%2B&source=bl&ots=LQ-5P_taoC&sig=lENUUIYBK53tZtTwNfHLy5PEWDk&hl=en&sa=X&ei=wezDUPW1J5DptQaMsIHQCw&redir_esc=y#v=onepage&q=fixed%20point%20method%20%20c%2B%2B&f=false Algebraically rearrange a solution to isolate a variable then apply incremental method Bisection method http://en.wikipedia.org/wiki/Bisection_method C++: http://numericalcomputing.wordpress.com/category/algorithms/ Bracketed - Select an initial interval, keep bisecting it ad midpoint into sub-intervals and then apply incremental method on smaller & smaller intervals – zoom in Adv: unaffected by function gradient à reliable Disadv: slow convergence False Position Method http://en.wikipedia.org/wiki/False_position_method C++: http://www.dreamincode.net/forums/topic/126100-bisection-and-false-position-methods/ Bracketed - Select an initial interval , & use the relative value of function at interval end points to select next sub-intervals (estimate how far between the end points the solution might be & subdivide based on this) Newton-Raphson method http://en.wikipedia.org/wiki/Newton's_method C++: http://www-users.cselabs.umn.edu/classes/Summer-2012/csci1113/index.php?page=./newt3 Also known as Newton's method Convenient, efficient Not bracketed – only a single initial guess is required to start iteration – requires an analytical expression for the first derivative of the function as input. Evaluates the function & its derivative at each step. Can be extended to the Newton MutiRoot method for solving multiple roots Can be easily applied to an of n-coupled set of non-linear equations – conduct a Taylor Series expansion of a function, dropping terms of order n, rewrite as a Jacobian matrix of PDs & convert to simultaneous linear equations !!! Secant Method http://en.wikipedia.org/wiki/Secant_method C++: http://forum.vcoderz.com/showthread.php?p=205230 Unlike N-R, can estimate first derivative from an initial interval (does not require root to be bracketed) instead of inputting it Since derivative is approximated, may converge slower. Is fast in practice as it does not have to evaluate the derivative at each step. Similar implementation to False Positive method Birge-Vieta Method http://mat.iitm.ac.in/home/sryedida/public_html/caimna/transcendental/polynomial%20methods/bv%20method.html C++: http://books.google.co.il/books?id=cL1boM2uyQwC&pg=SA3-PA51&lpg=SA3-PA51&dq=Birge-Vieta+Method+c%2B%2B&source=bl&ots=QZmnDTK3rC&sig=BPNcHHbpR_DKVoZXrLi4nVXD-gg&hl=en&sa=X&ei=R-_DUK2iNIjzsgbE5ID4Dg&redir_esc=y#v=onepage&q=Birge-Vieta%20Method%20c%2B%2B&f=false combines Horner's method of polynomial evaluation (transforming into lesser degree polynomials that are more computationally efficient to process) with Newton-Raphson to provide a computational speed-up Interpolation Overview Construct new data points for as close as possible fit within range of a discrete set of known points (that were obtained via sampling, experimentation) Use Taylor Series Expansion of a function f(x) around a specific value for x Linear Interpolation http://en.wikipedia.org/wiki/Linear_interpolation C++: http://www.hamaluik.com/?p=289 Straight line between 2 points à concatenate interpolants between each pair of data points Bilinear Interpolation http://en.wikipedia.org/wiki/Bilinear_interpolation C++: http://supercomputingblog.com/graphics/coding-bilinear-interpolation/2/ Extension of the linear function for interpolating functions of 2 variables – perform linear interpolation first in 1 direction, then in another. Used in image processing – e.g. texture mapping filter. Uses 4 vertices to interpolate a value within a unit cell. Lagrange Interpolation http://en.wikipedia.org/wiki/Lagrange_polynomial C++: http://www.codecogs.com/code/maths/approximation/interpolation/lagrange.php For polynomials Requires recomputation for all terms for each distinct x value – can only be applied for small number of nodes Numerically unstable Barycentric Interpolation http://epubs.siam.org/doi/pdf/10.1137/S0036144502417715 C++: http://www.gamedev.net/topic/621445-barycentric-coordinates-c-code-check/ Rearrange the terms in the equation of the Legrange interpolation by defining weight functions that are independent of the interpolated value of x Newton Divided Difference Interpolation http://en.wikipedia.org/wiki/Newton_polynomial C++: http://jee-appy.blogspot.co.il/2011/12/newton-divided-difference-interpolation.html Hermite Divided Differences: Interpolation polynomial approximation for a given set of data points in the NR form - divided differences are used to approximately calculate the various differences. For a given set of 3 data points , fit a quadratic interpolant through the data Bracketed functions allow Newton divided differences to be calculated recursively Difference table Cubic Spline Interpolation http://en.wikipedia.org/wiki/Spline_interpolation C++: https://www.marcusbannerman.co.uk/index.php/home/latestarticles/42-articles/96-cubic-spline-class.html Spline is a piecewise polynomial Provides smoothness – for interpolations with significantly varying data Use weighted coefficients to bend the function to be smooth & its 1st & 2nd derivatives are continuous through the edge points in the interval Curve Fitting A generalization of interpolating whereby given data points may contain noise à the curve does not necessarily pass through all the points Least Squares Fit http://en.wikipedia.org/wiki/Least_squares C++: http://www.ccas.ru/mmes/educat/lab04k/02/least-squares.c Residual – difference between observed value & expected value Model function is often chosen as a linear combination of the specified functions Determines: A) The model instance in which the sum of squared residuals has the least value B) param values for which model best fits data Straight Line Fit Linear correlation between independent variable and dependent variable Linear Regression http://en.wikipedia.org/wiki/Linear_regression C++: http://www.oocities.org/david_swaim/cpp/linregc.htm Special case of statistically exact extrapolation Leverage least squares Given a basis function, the sum of the residuals is determined and the corresponding gradient equation is expressed as a set of normal linear equations in matrix form that can be solved (e.g. using LU Decomposition) Can be weighted - Drop the assumption that all errors have the same significance –-> confidence of accuracy is different for each data point. Fit the function closer to points with higher weights Polynomial Fit - use a polynomial basis function Moving Average http://en.wikipedia.org/wiki/Moving_average C++: http://www.codeproject.com/Articles/17860/A-Simple-Moving-Average-Algorithm Used for smoothing (cancel fluctuations to highlight longer-term trends & cycles), time series data analysis, signal processing filters Replace each data point with average of neighbors. Can be simple (SMA), weighted (WMA), exponential (EMA). Lags behind latest data points – extra weight can be given to more recent data points. Weights can decrease arithmetically or exponentially according to distance from point. Parameters: smoothing factor, period, weight basis Optimization Overview Given function with multiple variables, find Min (or max by minimizing –f(x)) Iterative approach Efficient, but not necessarily reliable Conditions: noisy data, constraints, non-linear models Detection via sign of first derivative - Derivative of saddle points will be 0 Local minima Bisection method Similar method for finding a root for a non-linear equation Start with an interval that contains a minimum Golden Search method http://en.wikipedia.org/wiki/Golden_section_search C++: http://www.codecogs.com/code/maths/optimization/golden.php Bisect intervals according to golden ratio 0.618.. Achieves reduction by evaluating a single function instead of 2 Newton-Raphson Method Brent method http://en.wikipedia.org/wiki/Brent's_method C++: http://people.sc.fsu.edu/~jburkardt/cpp_src/brent/brent.cpp Based on quadratic or parabolic interpolation – if the function is smooth & parabolic near to the minimum, then a parabola fitted through any 3 points should approximate the minima – fails when the 3 points are collinear , in which case the denominator is 0 Simplex Method http://en.wikipedia.org/wiki/Simplex_algorithm C++: http://www.codeguru.com/cpp/article.php/c17505/Simplex-Optimization-Algorithm-and-Implemetation-in-C-Programming.htm Find the global minima of any multi-variable function Direct search – no derivatives required At each step it maintains a non-degenerative simplex – a convex hull of n+1 vertices. Obtains the minimum for a function with n variables by evaluating the function at n-1 points, iteratively replacing the point of worst result with the point of best result, shrinking the multidimensional simplex around the best point. Point replacement involves expanding & contracting the simplex near the worst value point to determine a better replacement point Oscillation can be avoided by choosing the 2nd worst result Restart if it gets stuck Parameters: contraction & expansion factors Simulated Annealing http://en.wikipedia.org/wiki/Simulated_annealing C++: http://code.google.com/p/cppsimulatedannealing/ Analogy to heating & cooling metal to strengthen its structure Stochastic method – apply random permutation search for global minima - Avoid entrapment in local minima via hill climbing Heating schedule - Annealing schedule params: temperature, iterations at each temp, temperature delta Cooling schedule – can be linear, step-wise or exponential Differential Evolution http://en.wikipedia.org/wiki/Differential_evolution C++: http://www.amichel.com/de/doc/html/ More advanced stochastic methods analogous to biological processes: Genetic algorithms, evolution strategies Parallel direct search method against multiple discrete or continuous variables Initial population of variable vectors chosen randomly – if weighted difference vector of 2 vectors yields a lower objective function value then it replaces the comparison vector Many params: #parents, #variables, step size, crossover constant etc Convergence is slow – many more function evaluations than simulated annealing Numerical Differentiation Overview 2 approaches to finite difference methods: · A) approximate function via polynomial interpolation then differentiate · B) Taylor series approximation – additionally provides error estimate Finite Difference methods http://en.wikipedia.org/wiki/Finite_difference_method C++: http://www.wpi.edu/Pubs/ETD/Available/etd-051807-164436/unrestricted/EAMPADU.pdf Find differences between high order derivative values - Approximate differential equations by finite differences at evenly spaced data points Based on forward & backward Taylor series expansion of f(x) about x plus or minus multiples of delta h. Forward / backward difference - the sums of the series contains even derivatives and the difference of the series contains odd derivatives – coupled equations that can be solved. Provide an approximation of the derivative within a O(h^2) accuracy There is also central difference & extended central difference which has a O(h^4) accuracy Richardson Extrapolation http://en.wikipedia.org/wiki/Richardson_extrapolation C++: http://mathscoding.blogspot.co.il/2012/02/introduction-richardson-extrapolation.html A sequence acceleration method applied to finite differences Fast convergence, high accuracy O(h^4) Derivatives via Interpolation Cannot apply Finite Difference method to discrete data points at uneven intervals – so need to approximate the derivative of f(x) using the derivative of the interpolant via 3 point Lagrange Interpolation Note: the higher the order of the derivative, the lower the approximation precision Numerical Integration Estimate finite & infinite integrals of functions More accurate procedure than numerical differentiation Use when it is not possible to obtain an integral of a function analytically or when the function is not given, only the data points are Newton Cotes Methods http://en.wikipedia.org/wiki/Newton%E2%80%93Cotes_formulas C++: http://www.siafoo.net/snippet/324 For equally spaced data points Computationally easy – based on local interpolation of n rectangular strip areas that is piecewise fitted to a polynomial to get the sum total area Evaluate the integrand at n+1 evenly spaced points – approximate definite integral by Sum Weights are derived from Lagrange Basis polynomials Leverage Trapezoidal Rule for default 2nd formulas, Simpson 1/3 Rule for substituting 3 point formulas, Simpson 3/8 Rule for 4 point formulas. For 4 point formulas use Bodes Rule. Higher orders obtain more accurate results Trapezoidal Rule uses simple area, Simpsons Rule replaces the integrand f(x) with a quadratic polynomial p(x) that uses the same values as f(x) for its end points, but adds a midpoint Romberg Integration http://en.wikipedia.org/wiki/Romberg's_method C++: http://code.google.com/p/romberg-integration/downloads/detail?name=romberg.cpp&can=2&q= Combines trapezoidal rule with Richardson Extrapolation Evaluates the integrand at equally spaced points The integrand must have continuous derivatives Each R(n,m) extrapolation uses a higher order integrand polynomial replacement rule (zeroth starts with trapezoidal) à a lower triangular matrix set of equation coefficients where the bottom right term has the most accurate approximation. The process continues until the difference between 2 successive diagonal terms becomes sufficiently small. Gaussian Quadrature http://en.wikipedia.org/wiki/Gaussian_quadrature C++: http://www.alglib.net/integration/gaussianquadratures.php Data points are chosen to yield best possible accuracy – requires fewer evaluations Ability to handle singularities, functions that are difficult to evaluate The integrand can include a weighting function determined by a set of orthogonal polynomials. Points & weights are selected so that the integrand yields the exact integral if f(x) is a polynomial of degree <= 2n+1 Techniques (basically different weighting functions): · Gauss-Legendre Integration w(x)=1 · Gauss-Laguerre Integration w(x)=e^-x · Gauss-Hermite Integration w(x)=e^-x^2 · Gauss-Chebyshev Integration w(x)= 1 / Sqrt(1-x^2) Solving ODEs Use when high order differential equations cannot be solved analytically Evaluated under boundary conditions RK for systems – a high order differential equation can always be transformed into a coupled first order system of equations Euler method http://en.wikipedia.org/wiki/Euler_method C++: http://rosettacode.org/wiki/Euler_method First order Runge–Kutta method. Simple recursive method – given an initial value, calculate derivative deltas. Unstable & not very accurate (O(h) error) – not used in practice A first-order method - the local error (truncation error per step) is proportional to the square of the step size, and the global error (error at a given time) is proportional to the step size In evolving solution between data points xn & xn+1, only evaluates derivatives at beginning of interval xn à asymmetric at boundaries Higher order Runge Kutta http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods C++: http://www.dreamincode.net/code/snippet1441.htm 2nd & 4th order RK - Introduces parameterized midpoints for more symmetric solutions à accuracy at higher computational cost Adaptive RK – RK-Fehlberg – estimate the truncation at each integration step & automatically adjust the step size to keep error within prescribed limits. At each step 2 approximations are compared – if in disagreement to a specific accuracy, the step size is reduced Boundary Value Problems Where solution of differential equations are located at 2 different values of the independent variable x à more difficult, because cannot just start at point of initial value – there may not be enough starting conditions available at the end points to produce a unique solution An n-order equation will require n boundary conditions – need to determine the missing n-1 conditions which cause the given conditions at the other boundary to be satisfied Shooting Method http://en.wikipedia.org/wiki/Shooting_method C++: http://ganeshtiwaridotcomdotnp.blogspot.co.il/2009/12/c-c-code-shooting-method-for-solving.html Iteratively guess the missing values for one end & integrate, then inspect the discrepancy with the boundary values of the other end to adjust the estimate Given the starting boundary values u1 & u2 which contain the root u, solve u given the false position method (solving the differential equation as an initial value problem via 4th order RK), then use u to solve the differential equations. Finite Difference Method For linear & non-linear systems Higher order derivatives require more computational steps – some combinations for boundary conditions may not work though Improve the accuracy by increasing the number of mesh points Solving EigenValue Problems An eigenvalue can substitute a matrix when doing matrix multiplication à convert matrix multiplication into a polynomial EigenValue For a given set of equations in matrix form, determine what are the solution eigenvalue & eigenvectors Similar Matrices - have same eigenvalues. Use orthogonal similarity transforms to reduce a matrix to diagonal form from which eigenvalue(s) & eigenvectors can be computed iteratively Jacobi method http://en.wikipedia.org/wiki/Jacobi_method C++: http://people.sc.fsu.edu/~jburkardt/classes/acs2_2008/openmp/jacobi/jacobi.html Robust but Computationally intense – use for small matrices < 10x10 Power Iteration http://en.wikipedia.org/wiki/Power_iteration For any given real symmetric matrix, generate the largest single eigenvalue & its eigenvectors Simplest method – does not compute matrix decomposition à suitable for large, sparse matrices Inverse Iteration Variation of power iteration method – generates the smallest eigenvalue from the inverse matrix Rayleigh Method http://en.wikipedia.org/wiki/Rayleigh's_method_of_dimensional_analysis Variation of power iteration method Rayleigh Quotient Method Variation of inverse iteration method Matrix Tri-diagonalization Method Use householder algorithm to reduce an NxN symmetric matrix to a tridiagonal real symmetric matrix vua N-2 orthogonal transforms     Whats Next Outside of Numerical Methods there are lots of different types of algorithms that I’ve learned over the decades: Data Mining – (I covered this briefly in a previous post: http://geekswithblogs.net/JoshReuben/archive/2007/12/31/ssas-dm-algorithms.aspx ) Search & Sort Routing Problem Solving Logical Theorem Proving Planning Probabilistic Reasoning Machine Learning Solvers (eg MIP) Bioinformatics (Sequence Alignment, Protein Folding) Quant Finance (I read Wilmott’s books – interesting) Sooner or later, I’ll cover the above topics as well.

    Read the article

1