CodeProject Latest postings for Algorithms
http://www.codeproject.com
Latest postings for Algorithms from CodeProjecten-usCodeProject Latest postings for Algorithmshttp://www.codeproject.com/App_Themes/Std/Img/logo100x30.gif
http://www.codeproject.com
10030CodeProjectCopyright CodeProject, 1999-2014Webmaster@codeproject.com (Webmaster)Sun, 14 Sep 2014 12:14:00 GMT20C# Hand-coded goodnessHOW TO ANSWER A QUESTIONApologies for the shouting but this is important.<br />
<br />
When answering a question please:<br />
<ol><li>Read the question carefully<br />
<li>Understand that English isn't everyone's first language so be lenient of bad spelling and grammar<br />
<li>If a question is poorly phrased then either ask for clarification, ignore it, or mark it down. <b>Insults are not welcome</b><br />
<li>If the question is inappropriate then click the 'vote to remove message' button<br />
</li></li></li></li></ol>
Insults, slap-downs and sarcasm aren't welcome. Let's work to help developers, not make them feel stupid. <br />
<br />
<div class="ForumSig">cheers,<br />
Chris Maunder<br />
<br />
The Code Project Co-founder<br />
Microsoft C++ MVP</div>
http://www.codeproject.com/Messages/3137503/HOW-TO-ANSWER-A-QUESTION.aspx
Chris MaunderTue, 28 Jul 2009 12:32:00 GMTAlgorithmsHow to get an answer to your questionFor those new to message boards please try to follow a few simple rules when posting your question.<ol><li><b>Choose the correct forum for your message</b>. Posting a VB.NET question in the C++ forum will end in tears.<br />
<br />
<li><b>Be specific!</b> Don't ask "can someone send me the code to create an application that does 'X'. Pinpoint exactly what it is you need help with.<br />
<br />
<li>Keep the subject line brief, but descriptive. eg "File Serialization problem"<br />
<br />
<li>Keep the question as brief as possible. If you have to include code, include the smallest snippet of code you can.<br />
<br />
<li>Be careful when including code that you haven't made a typo. Typing mistakes can become the focal point instead of the actual question you asked.<br />
<br />
<li><b>Do not remove or empty a message</b> if others have replied. Keep the thread intact and available for others to search and read. If your problem was answered then edit your message and add "[Solved]" to the subject line of the original post, and cast an approval vote to the one or several answers that really helped you.<br />
<br />
<li>If you are posting source code with your question, place it inside <pre></pre> tags. We advise you also check the "Encode "<" (and other HTML) characters when pasting" checkbox before pasting anything inside the PRE block, and make sure "Use HTML in this post" check box is checked.<br />
<br />
<li>Be courteous and DON'T SHOUT. Everyone here helps because they enjoy helping others, not because it's their job.<br />
<br />
<li>Please do not post links to your question into an unrelated forum such as the lounge. It will be deleted. Likewise, do not post the same question in more than one forum.<br />
<br />
<li>Do not be abusive, offensive, inappropriate or harass anyone on the boards. Doing so will get you kicked off and banned. Play nice.<br />
<br />
<li>If you have a school or university assignment, assume that your teacher or lecturer is also reading these forums. <br />
<br />
<li>No advertising or soliciting.<br />
<br />
<li>We reserve the right to move your posts to a more appropriate forum or to delete anything deemed inappropriate or illegal.</li></li></li></li></li></li></li></li></li></li></li></li></li></ol>
<div class="signature">cheers,<br />
Chris Maunder<br />
<br />
The Code Project Co-founder<br />
<div class="SmallText">Microsoft C++ MVP</div></div>
http://www.codeproject.com/Messages/2966804/How-to-get-an-answer-to-your-question.aspx
Chris MaunderMon, 16 Mar 2009 20:13:00 GMTAlgorithmsOptimizing memory usageFor my old computer I need an assembler which is able to take assembled code from a library and link it together in the smallest possible combination. <br />
<br />
One 'speciality' of the old CDP1802 processor will force me to write the assembler and linker myself. There are two types of branching instructions: long branches and short branches. Long branches use full 16 bit addresses, but will cause timing issues with the graphics chip. This is an ancient hardware bug. <br />
<br />
This is the reason why i must use short branches with short 8 bit addresses. The upper 8 bits are just assumed to remain the same as in the instruction's address. This way memory is segmented into 256 byte blocks. It's not a very strict segmentation as the code can run across the boundaries without any consequences, You just can't loop back with a short branch and long branches can't be used.<br />
<br />
The linker will have to puzzle together snippets of code and data with this in mind. At the same time I must be sure that memory usage is as low as possible in the end. My old computer has only 4k RAM, and more than 16k is quite unusual.<br />
<br />
The only thing I can think of is to make a memory map of each possible combination and take the one which needs the least amount of memory. There are easily hundreds of small code snippets to be linked and blindly testing every combination will be very slow and inefficient.<br />
<br />
First thought: Build a tree with only valid options and then find the branch with the lowest byte count. This is alresy better than brute force, but I hope there is still a more elegant algorithm for this.<br />
<div class="signature">The language is JavaScript. that of Mordor, which I will not utter here<br /><br />
I hold an A-7 computer expert classification, Commodore. I'm well acquainted with Dr. Daystrom's theories and discoveries. The basic design of all our ship's computers are JavaScript. </div>
http://www.codeproject.com/Messages/4902681/Optimizing-memory-usage.aspx
CDP1802Sun, 14 Sep 2014 12:14:00 GMTAlgorithmsHow .NET CLR understands More languagesHi all there,<br />
<br />
I need to understatnd that How .NET CLR understands different languages at once and make MSIL (universal code or common code) to ASP.NET engine(i mean in web app)<br />
<br />
<br />
Thanks in advance<br />
Pitchaiyan C
http://www.codeproject.com/Messages/4901998/How-NET-CLR-understands-More-languages.aspx
pitchaiyanFri, 12 Sep 2014 15:12:00 GMTAlgorithmsAlgorithm to find a given number is prime or not.Hi friends, need help!! i am absloute beginner and need advise. below algorithm is an extrat from a text book but when i try to apply and solve the problem on paper i see that this algorithm will fail. as i get a remainder 0 every digit i key in till 8 (i took number 8 as an examole and applied below)...please advise....also i found that applying this algorithm on number 2 would result in 0 as well and if it is 0 then not prime, then how is this algorithm correct!<br />
<br />
1 start<br />
2 read the number num<br />
3 [initialize]<br />
i <--2, flag <--1<br />
4 repeatnsteps 4 through 6 unitl i <num or="" flag="0" 5="" rem=""></num>
http://www.codeproject.com/Messages/4897654/Algorithm-to-find-a-given-number-is-prime-or-not.aspx
Member 11063123Sat, 06 Sep 2014 11:21:00 GMTAlgorithmsHow to describe method: SQL for frequent pattern discoveryI've prototyped a way to do pattern discovery using SQL, but I still have a poor understanding of where this method fits in the data mining vernacular.<br /> <br />Being set-based, I'm not building a tree, although a functional tree does arise in the result set. <br /> <br />The steps:<br /> <br />1) Build a "look up" table, by doing a cross join, yielding a combinatorial "dictionary" (a rainbow table) of n-gram "words."<br /> <br />2) Get COUNT(*) > n , using SQL GROUP BY, matched against a large table of items<br /> <br />3) Further look for equivalent longer self-matches within the result set.<br /> <br />My seed table is 177 items, allowed to cross-join itself 3x, for a final table 2.8 million 3-gram words (takes about 35 seconds to build this table in Postgres). <br /> <br />The actual itemset table is 10 million rows in series (serially numbered), although the actual number of itemsets might be considered smaller. <br /> <br />I've recorded 35** seconds on the join between the two original tables, yielding all the simple repeating 3-grams meeting group by's count(*) > x (that's the dictionary joined to the itemsets. <br /> <br />That's the Q&D discovery step, and then subsequent steps simply apply a self-join for longer-chained repeating series. These have been pretty quick, in the 50 millisecond range. <br /> <br />My questions are:<br /> <br />1) What's the best way to describe this algorithm? Frequent pattern? Motif? <br /> <br />2) It's a simple enough method, but is it fast enough for general use? I.e. other data mining apps where performance requirements are different from my own?<br /> <br />3) I've wondered if SQL could be convinced to pattern-match like an LCS dynamic programming algorithm, by matching across gaps in the sequence, with maybe a lookup table of allowable variances & distance between matching values?<br /> <br /><br />**Right now I'm seeing 50 seconds after the buffers load, but I reinstalled Postgres & my postgres.conf file apparently is all defaults now (the postgres process back to only 16 mb getting buffered, so it's suffering more I/O to the SSD drive). <br /> <br />Thanks in advance,<br /> <br />-- Lee
http://www.codeproject.com/Messages/4896681/How-to-describe-method-SQL-for-frequent-pattern-di.aspx
Member 11060173Fri, 05 Sep 2014 04:01:00 GMTAlgorithmsBoundless Binary SearchI've been playing around with binary search algorithms and have created a novel new variant that appears to be significantly faster than any traditional implementations I've seen.<br />
<br />
<pre lang="c++"><span class="code-keyword">int</span> boundless_binary_search(<span class="code-keyword">int</span> *<span class="code-keyword">array</span>, <span class="code-keyword">int</span> array_size, <span class="code-keyword">int</span> key)
{
<span class="code-keyword">register</span> <span class="code-keyword">int</span> mid, i;
mid = i = array_size - <span class="code-digit">1</span>;
<span class="code-keyword">while</span> (mid > <span class="code-digit">7</span>)
{
mid = mid / <span class="code-digit">2</span>;
<span class="code-keyword">if</span> (key < <span class="code-keyword">array</span>[i - mid]) i -= mid;
}
<span class="code-keyword">while</span> (i && key < <span class="code-keyword">array</span>[i]) --i;
<span class="code-keyword">if</span> (key == <span class="code-keyword">array</span>[i])
{
<span class="code-keyword">return</span> i;
}
<span class="code-keyword">return</span> -<span class="code-digit">1</span>;
}</pre>
<br />
I'm wondering if this is a novel binary search implementation, or has this approach been used by someone before?<br />
<br />
Some variants and benchmark graphs:<br />
<br />
<a href="https://sites.google.com/site/binarysearchcube/binary-search">https://sites.google.com/site/binarysearchcube/binary-search</a>[<a href="https://sites.google.com/site/binarysearchcube/binary-search" target="_blank" title="New Window">^</a>]
http://www.codeproject.com/Messages/4891263/Boundless-Binary-Search.aspx
Gregorius van den HovenWed, 27 Aug 2014 20:24:00 GMTAlgorithmsSurface calculation (sphere) - projection effect. [SOLVED ?]I want to calculate the surface of an area on a sphere including projection effect.<br />
For this I have a scanned image (which results in a 2D disc). On this image I can highlight an area and I have the index of each pixel of that area relative to the center of that disc (x, y coordinates). I also have the radius (in pixels and meters)<br />
<br />
How can I calculate the correction needed for each pixel in order to take in account the projection effect (larger at the edges of the disc)?<br />
<br />
Thanks.<br />
<br />
<i>[SOLUTION]</i><br />
It's a pretty long solution, so I'll try to be as brief as possible.<br />
1. You need to scale down the sphere to a unit sphere (<b>radius=1</b>)<br />
2. With that you know that x²+y²+z² = 1 and thus z = sqrt(1-x²-y²) and the surface (of a full sphere) is 4*pi*r² = 4*pi, but you only have half the sphere so S=2*pi<br />
3. What you need is the cosine of the angle of the pixel with the Z-axis. This is the z calculated in step 2 (the sqrt) divided by the radius which you reduced to one.<br />
4. In the end you get this formula for the area per pixel: (1/r² * 1/(2*pi*sqrt(1-x²-y²)) ). If you loop through the pixels of the complete area you just need to to sum up all these pixels.<br />
5. This results in a fraction of the surface compared to the sphere surface which you can then convert to any unit you like.<br />
On first sight this "looks" correct <img src="https://dj9okeyxktdvd.cloudfront.net/script/Forums/Images/smiley_smile.gif" align="top" alt="Smile | :)" /> <br />
<i>[/SOLUTION]</i><br />
<div class="signature">V.<br /><br />
<small>(MQOTD <a href="http://www.codeproject.com/Members/VnotforVendetta?fid=40050&select=4732397&tid=4369832" target="_blank">rules</a> and <a href="http://www.codeproject.com/script/Membership/View.aspx?mid=1008736&fid=40050&tid=4732397" target="_blank">previous solutions</a>)</small></div>
http://www.codeproject.com/Messages/4875255/Surface-calculation-sphere-projection-effect-SOLVE.aspx
V.Mon, 04 Aug 2014 08:31:00 GMTAlgorithmsLock free algorithmsI've been studying lock free algorithms, specifically the circular lock free ring buffer. I fully understand what they're doing, but am having trouble applying that to some of my code. It seems that the lock free ring buffer is meant for situations where the queue is neither starved nor saturated for any "significant" (in CPU terms) period of time.<br />
<br />
For example, I recently had some code with multiple producers and a single consumer. When the server was running at a normal load, the lock free ring buffer would have been an excellent solution. However, when the server load was low it seems the consumer would just be spinning, using quite a bit of CPU doing nothing. Contra-wise, when the server load was high, the producers would be spinning (in the current code, if this happens, the producers have a wait of a certain period at which point, they discard their data and grab the next set [losing data periodically was permissible since the next set would allow a full reconstruction, albeit with stutter]), but how long do they spin? Can't use just a count since time is important in this situation, but grabbing clock is expensive and simply looping the thread consumes a lot of CPU, depriving other producers of their quanta.<br />
<br />
Am I missing something?
http://www.codeproject.com/Messages/4852770/Lock-free-algorithms.aspx
Joe WoodburyTue, 01 Jul 2014 18:15:00 GMTAlgorithmsAlgorithm for comparing word with randomly distributed substringHello,<br />
<br />
I'm facing a strange problem. I have a word for example "ABCDE". I want to match this word againsta sentence like "ABC EFGH IJKL DE". As you can see, the query word is splited and distributed across the senetence. How can I design algorithm which can give me result like the query word has acombination in the sentence and their position.<br />
<br />
<br />
An example;<br />
<br />
QUERY word: ABCDEF<br />
TARGET sentence: EFGH UIOP ABC GHY JKLU EF<br />
<br />
I expect the output as the query word has a perfect match by the combining words 3,6.<br />
<br />
I tried several algorithms like smithwatermann, levenstein distance and others, but I could figure out how I can compare string with randomly distributed sub-strings in a sentence.<br />
<br />
<br />
One way of doing is, breaking sentence into words and make all possible combinations and start matching with query which would take forever if I have 500 words.<br />
<br />
Any help or suggestion would be highly appreciated.
http://www.codeproject.com/Messages/4852205/Algorithm-for-comparing-word-with-randomly-distrib.aspx
srikanth2321Tue, 01 Jul 2014 09:06:00 GMTAlgorithmsCubesortI've created a new sorting algorithm which allows O(1) sorting of ordered data, O(log (root n)) sorting of partially sorted data, and O(log n) sorting of random data.<br />
<br />
The underlying mechanism is well suited for a general purpose data structure, which I'm calling a binary search cube, and has notable advantages over binary trees. The data structure is cube-shaped rather than tree-shaped.<br />
<br />
I've described the data structure and sorting algorithm on the following webpage:<br />
<br />
<a href="https://sites.google.com/site/binarysearchcube/">https://sites.google.com/site/binarysearchcube/</a><br />
<br />
The site also includes three programs written in C, one of them implementing cubesort using a 4 dimensional search cube, and an implementation of a 3 and 4 dimensional binary search cube.<br />
<br />
Haven't been able to properly benchmark the software against other sorting algorithms and data structures, but the memory overhead is significantly less.<br />
<br />
Hoping for some interesting feedback.
http://www.codeproject.com/Messages/4846424/Cubesort.aspx
Gregorius van den HovenSun, 22 Jun 2014 14:09:00 GMTAlgorithmsReduce a Q2SAT formulaHow to reduce a quantified 2 Sat formula to a quantified horn formula?
http://www.codeproject.com/Messages/4842088/Reduce-a-Q-SAT-formula.aspx
ApurvguptaMon, 16 Jun 2014 06:48:00 GMTAlgorithmsFastest textual decompression in CGuys, <br />
for 25 or so days I have been wrestling with the most simple approach in LZSS.<br />
Seeing how demanding (criticizing) are some fellow members, here I would like to hear from all interested in this topic programmers what one good article about LZSS should feature.<br />
So, please share here your point on what has to be covered what to be emphasized and other must-be-s in the article.<br />
<br />
Maybe I will write an article, the thing that stops me is the unappreciativeness. My way of doing things is all about enjoying the speeds of small etudes in C, that's why I ask preemptively:<br />
Does CODEPROJECT need the article 'Fastest textual decompression in C'?. <br />
<br />
Here you can see my etude heavily benchmarked against the best in the world:<br />
<a href="http://www.sanmayce.com/Nakamichi/">http://www.sanmayce.com/Nakamichi/</a>[<a href="http://www.sanmayce.com/Nakamichi/" target="_blank" title="New Window">^</a>]
http://www.codeproject.com/Messages/4817931/Fastest-textual-decompression-in-C.aspx
SanmayceSat, 10 May 2014 18:54:00 GMTAlgorithmsThe Bessel-Overhauser Spline interpolation - suitable values for the weight functionThe formula that I'm using to create this is from the book "Mathematical tools in computer graphics with C# implementation", however it only had the formula and no code. You could find the same kind of formulations available online <a href="http://www.cs.sjsu.edu/faculty/pollett/216.1.10s/Lec16022010.html#%284%29">here</a>[<a href="http://www.cs.sjsu.edu/faculty/pollett/216.1.10s/Lec16022010.html#%284%29" target="_blank" title="New Window">^</a>], and skipback and forwards on the slides to see a bit more.<br />
<br />
My Implementation looks like this:<br />
<pre lang="vb"><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">summary</span><span class="code-summarycomment">></span>
</span><span class="code-summarycomment">'''</span><span class="code-comment"> The Bessel-Overhauser Spline interpolation
</span><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">/</span><span class="code-summarycomment">summary</span><span class="code-summarycomment">></span>
</span><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">param</span> <span class="code-summarycomment">name="p0"</span><span class="code-summarycomment">></span>First point<span class="code-summarycomment"><</span><span class="code-summarycomment">/</span><span class="code-summarycomment">param</span><span class="code-summarycomment">></span>
</span><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">param</span> <span class="code-summarycomment">name="p1"</span><span class="code-summarycomment">></span>Second point<span class="code-summarycomment"><</span><span class="code-summarycomment">/</span><span class="code-summarycomment">param</span><span class="code-summarycomment">></span>
</span><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">param</span> <span class="code-summarycomment">name="p2"</span><span class="code-summarycomment">></span>Third point<span class="code-summarycomment"><</span><span class="code-summarycomment">/</span><span class="code-summarycomment">param</span><span class="code-summarycomment">></span>
</span><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">param</span> <span class="code-summarycomment">name="p3"</span><span class="code-summarycomment">></span>Forth point<span class="code-summarycomment"><</span><span class="code-summarycomment">/</span><span class="code-summarycomment">param</span><span class="code-summarycomment">></span>
</span><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">param</span> <span class="code-summarycomment">name="t"</span><span class="code-summarycomment">></span><span class="code-summarycomment"><</span><span class="code-summarycomment">/</span><span class="code-summarycomment">param</span><span class="code-summarycomment">></span>
</span><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">param</span> <span class="code-summarycomment">name="u"</span><span class="code-summarycomment">></span>The value from 0 - 1 where 0 is the start of the curve (globally) and 1 is the end of the curve (globally)<span class="code-summarycomment"><</span><span class="code-summarycomment">/</span><span class="code-summarycomment">param</span><span class="code-summarycomment">></span>
</span><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">returns</span><span class="code-summarycomment">></span><span class="code-summarycomment"><</span><span class="code-summarycomment">/</span><span class="code-summarycomment">returns</span><span class="code-summarycomment">></span>
</span><span class="code-summarycomment">'''</span><span class="code-comment"> <span class="code-summarycomment"><</span><span class="code-summarycomment">remarks</span><span class="code-summarycomment">></span><span class="code-summarycomment"><</span><span class="code-summarycomment">/</span><span class="code-summarycomment">remarks</span><span class="code-summarycomment">></span>
</span><span class="code-keyword">Public</span> <span class="code-keyword">Function</span> PointOnBesselOverhauserCurve(<span class="code-keyword">ByVal</span> p0 <span class="code-keyword">As</span> System.Windows.Point, <span class="code-keyword">ByVal</span> p1 <span class="code-keyword">As</span> System.Windows.Point, <span class="code-keyword">ByVal</span> p2 <span class="code-keyword">As</span> System.Windows.Point, <span class="code-keyword">ByVal</span> p3 <span class="code-keyword">As</span> System.Windows.Point, <span class="code-keyword">ByVal</span> t() <span class="code-keyword">As</span> <span class="code-keyword">Double</span>, <span class="code-keyword">ByVal</span> u <span class="code-keyword">As</span> <span class="code-keyword">Double</span>) <span class="code-keyword">As</span> System.Windows.Point
<span class="code-keyword">Dim</span> result <span class="code-keyword">As</span> <span class="code-keyword">New</span> System.Windows.Point()
<span class="code-keyword">Dim</span> ViXPlusHalf, VixMinusHalf, ViYPlusHalf, ViYMinusHalf, ViX, ViY <span class="code-keyword">As</span> <span class="code-keyword">Double</span>
ViXPlusHalf = (p2.X - p1.X) / (t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>))
VixMinusHalf = (p1.X - p0.X) / (t(<span class="code-digit">1</span>) - t(<span class="code-digit">0</span>))
ViYPlusHalf = (p2.Y - p1.Y) / (t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>))
ViYMinusHalf = (p1.Y - p0.Y) / (t(<span class="code-digit">1</span>) - t(<span class="code-digit">0</span>))
ViX = ((t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>)) * VixMinusHalf + (t(<span class="code-digit">1</span>) - t(<span class="code-digit">0</span>)) * ViXPlusHalf) / (t(<span class="code-digit">2</span>) - t(<span class="code-digit">0</span>))
ViY = ((t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>)) * ViYMinusHalf + (t(<span class="code-digit">1</span>) - t(<span class="code-digit">0</span>)) * ViYPlusHalf) / (t(<span class="code-digit">2</span>) - t(<span class="code-digit">0</span>))
<span class="code-comment">'</span><span class="code-comment"> Location of Controlpoints
</span> <span class="code-keyword">Dim</span> PointList <span class="code-keyword">As</span> <span class="code-keyword">New</span> PointCollection
PointList.Add(p1)
PointList.Add(<span class="code-keyword">New</span> Point(p1.X + (<span class="code-digit">1</span> / <span class="code-digit">3</span>) * (t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>)) * ViX, p1.Y + (<span class="code-digit">1</span> / <span class="code-digit">3</span>) * (t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>)) * ViY))
ViXPlusHalf = (p3.X - p2.X) / (t(<span class="code-digit">3</span>) - t(<span class="code-digit">2</span>))
VixMinusHalf = (p2.X - p1.X) / (t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>))
ViYPlusHalf = (p3.Y - p2.Y) / (t(<span class="code-digit">3</span>) - t(<span class="code-digit">2</span>))
ViYMinusHalf = (p2.Y - p1.Y) / (t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>))
ViX = ((t(<span class="code-digit">3</span>) - t(<span class="code-digit">2</span>)) * VixMinusHalf + (t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>)) * ViXPlusHalf) / (t(<span class="code-digit">3</span>) - t(<span class="code-digit">1</span>))
ViY = ((t(<span class="code-digit">3</span>) - t(<span class="code-digit">2</span>)) * ViYMinusHalf + (t(<span class="code-digit">2</span>) - t(<span class="code-digit">1</span>)) * ViYPlusHalf) / (t(<span class="code-digit">3</span>) - t(<span class="code-digit">1</span>))
PointList.Add(<span class="code-keyword">New</span> Point(p2.X - (<span class="code-digit">1</span> / <span class="code-digit">3</span>) * (t(<span class="code-digit">3</span>) - t(<span class="code-digit">2</span>)) * ViX, p2.Y - (<span class="code-digit">1</span> / <span class="code-digit">3</span>) * (t(<span class="code-digit">3</span>) - t(<span class="code-digit">2</span>)) * ViY))
PointList.Add(p2)
<span class="code-comment">'</span><span class="code-comment"> Get the calcualted value from the 3rd degree Bezier curve
</span> <span class="code-keyword">Return</span> PointBezierFunction(PointList, u)
<span class="code-keyword">End</span> <span class="code-keyword">Function</span></pre>
<br />
I assumed that t(), and array of equal length to the number of points, would be the same in both X and Y directions. Now, how should adjust my t() values, and should they be dependent on the values X and Y, meaning that they have one value for X and one value for Y? And, is the implementation correct?
http://www.codeproject.com/Messages/4793428/The-Bessel-Overhauser-Spline-interpolation-suitabl.aspx
Kenneth HauglandFri, 04 Apr 2014 09:34:00 GMTAlgorithmsFactoring algorithmDoes anyone have any comment on my factoring algo below:<br /> <br />A new method to factor large semi primes.<br /> <br />The plan is to factor large semi prime numbers. Start by picking 2 Prime Numbers of<br />appropriate digit size. Choose one as a 200 digit Prime Number, and the other as a 300<br />digit Prime Number, where their product would be a 500 digit prime number. Then convert<br />the two decimal digit prime numbers to binary values, and multiply them to form the binary<br />semi prime product. Calculate the bit size of the binary product. Save a copy of this semi<br />prime into another value whose bit size is the size of the semi prime rounded up to a<br />DWORD (mod 32 bit) bound, but left shift it until it fills the largest DWORD. Then save<br />another copy of this left shifted semi prime, but this time right shifted by 1 bit. These<br />copies of the semi prime will be used to compare the products of the highest test DWORDS<br />calculated in the algorithm below (see below for the explanation of why two copies are<br />used).<br /> <br />The semi prime product would then be factored using a new algorithm.<br /> <br />It has been suggested (by S. C. Coutinho in "The Mathemetics of Cipher", Chapter 11) that<br />to select the prime numbers for a key of a digit size of r, select one between a digit<br />size of ((4 / 10) * r) and ((45 / 100) * r). The starting point for the factoring will be<br />chosen as the middle value between these limits, and will step alternately higher and<br />lower until the factors are discovered. The first starting factor will then be the p (the<br />smaller number), and the other starting factor will be q (the larger number) which will be<br />set to ((10^r ) / p).<br /> <br />With an r of 500, the lowest limit (in digits) will be:<br /> <br /> p = ((4 / 10) * r)<br /> p = ((4 / 10) * 500)<br /> p = (4 * 50)<br /> p = 200 digits<br /> <br />The upper limit will be:<br /> <br /> p = ((45 / 100) * r)<br /> p = ((45 / 100) * 500)<br /> p = (45 * 5)<br /> p = 225 digits<br /> <br />The mid-point will be:<br /> <br /> P = ((200 + 225) / 2)<br /> p = 212 digits<br /> <br />Thus the starting p is a 212 digit number. The other starting factor will be:<br /> <br /> q = ((10^r) / p)<br /> q = ((10^500) / (10^212))<br /> q = 288 digits<br /> <br />The p value is then the calculated digit size (converted to bits and then DWORDS), but<br />the q value must be calculated by subtracting the selected p value bit size from the<br />selected semi prime bit size (and then rounded up to DWORDS). These bit sizes define bit<br />fields that will be filled in from both ends with actual values during the factoring<br />process.<br /> <br />The bit size, digit size, and DWORD sizes of these values are as follows (all of these<br />powers of 2 are the largest exponent that would not exceed the associated power of 10,<br />and the DWORD count is the minimum count of DWORDS to contain that binary bit count):<br /> <br /> 2^707 = 10^212 = 23 DWORDS starting low<br /> 2^960 = 10^288 = 30 DWORDS starting high<br /> 2^999 = 10^300 = 32 DWORDS max high<br /> 2^1664 = 10^500 = 52 DWORDS max product<br /> <br />Three sets of pre-computed tables must be constructed to aid (actually enable) the<br />factoring of this semi prime.<br /> <br />The first table is saved as 32 bit odd factors (DWORDS), which, when multiplied and<br />masked to a DWORD, give the same masked product value. This table is saved as multiple<br />files with names matching the masked product value.<br /> <br />A second, similar, table is constructed for factors which all have the most significant<br />bit set and saved as files with names matching the highest 32 bits of the product value<br />(masked to 32 bits).<br /> <br />The third table is just a list of the prime numbers to be considered (all prime numbers<br />less than 300 decimal digits), but saved in a special way as a multi-level directory<br />structure as described below.<br /> <br />The entries for this third table consist of DWORD pairs where one of the DWORDS is the<br />lowest DWORD of the prime number and the other DWORD is the highest 32 bits of the prime<br />number. All prime numbers that share both of these end values and have the same bit size<br />will be saved in a directory whose name matches the two DWORDS (high DWORD value and low<br />DWORD value). The directory sets will be saved under a directory that relates to the bit<br />size.<br /> <br />One bit of explanation about the information that follows. When a string is enclosed in<br />quotation marks (""), it is an encoded alphanumeric string. When the characters are not<br />enclosed in quotes, then the characters are treated as independent decoded DWORD values.<br /> <br />At this point, a diagram may be appropriate. Consider a large prime number with DWORDS<br />indicated as Hx and Lx, and bit size as a 3 BYTE value indicated by Sx:<br /> <br /> H1 H2 H3 H4 ... L4 L3 L2 L1 length Sx<br /> <br />The lowest level directory structure would be (where "Sx" are the different prime number<br />bit sizes from 2 to 1664):<br /> <br /> "Sx"<br /> "Sy"<br /> ...<br /> "Sz"<br /> <br />Beneath each of these size directories would be a layer of directories named "H1x L1x"<br />(whose prime number bit size is "Sx" and where "H1x" and "L1x" are the first level<br />different highest and lowest DWORD values of the semi prime):<br /> <br /> "H1x L1x"<br /> "H1y L1y"<br /> ...<br /> "H1z L1z"<br /> <br />Beneath each of these directories would be another layer of directories named "H2x L2x":<br /> <br /> "H2x L2x"<br /> "H2y L2y"<br /> ...<br /> "H2z L2z"<br /> <br />Essentially, you are creating piecemeal path names on some drive or drives (at some<br />directory level) as a relative path name:<br /> <br /> ".\Sx\H1x L1x\H2x L2x\H3x L3x\H4x L4x\ ..."<br /> ".\Sx\H1y L1y\H2y L2y\H3y L3y\H4y L4y\ ...<br /> ...<br /> ".\Sx\H1z L1z\H2z L2z\H3z L3z\H4z L4z\ ..."<br /> <br /> ".\Sy\H1x L1x\H2x L2x\H3x L3x\H4x L4x\ ..."<br /> ".\Sy\H1y L1y\H2y L2y\H3y L3y\H4y L4y\ ...<br /> ...<br /> ".\Sy\H1z L1z\H2z L2z\H3z L3z\H4z L4z\ ..."<br /> <br /> ".\Sz\H1x L1x\H2x L2x\H3x L3x\H4x L4x\ ..."<br /> ".\Sz\H1y L1y\H2y L2y\H3y L3y\H4y L4y\ ...<br /> ...<br /> ".\Sz\H1z L1z\H2z L2z\H3z L3z\H4z L4z\ ..."<br /> <br />One other thing to note is that this method greatly reduces the duplication of some of<br />the DWORD values that would otherwise occur if the actual prime numbers were given as<br />just a list of full N digit values, i.e., consider 32 DWORD prime numbers of the<br />following form (where each prime number contained the same low 4 DWORDS and same high 4<br />DWORDS):<br /> <br /> H1 H2 H3 H4 ... ... ... L4 L3 L2 L1<br /> <br />The "... ... ..." represent 24 DWORDS, some of which must be different (remember, this<br />is from a list of prime numbers that are all unique), yet H1 H2 H3 H4 and L4 L3 L2 L1<br />DWORDS would all be the same and thus not duplicated in this level structure. In the<br />maximum duplication form, the H1 through H15 and L1 through L15 DWORDS could all be the<br />same, and only the H16 and L16 DWORDS would be different.<br /> <br />Note that the data is not really binary data, but directory names which must be formed<br />with alphanumeric or special characters. What will be done to reduce the size of the data<br />is that the numeric DWORD values will be converted to encoded character values. Several<br />things were considered in this quest. If decimal conversion were done (0-9), then the<br />DWORDS would need 10 characters for each DWORD or 20 characters total. If 4 bit hex<br />conversions were used (0-9 and A-F), then the DWORDS would need 8 characters for each<br />DWORD or 16 characters total. If 6 bit ASCII64 encoding were used, then the DWORDS would<br />need 6 characters for each DWORD or 12 characters total but the resulting upper and lower<br />case letters would require the use of Unicode filenames, and this alone would double the<br />size of the data to 24 BYTES. Using a character set of upper case and numeric characters<br />and allowed special characters (26 + 10 + 16 or a 52 character conversion set) would allow<br />6 character conversions for each DWORD or 12 characters total, but would require divisions<br />to be used to extract the actual character indexes. Using a 32 character conversion set<br />(A-Z and 0-5) would result in 7 character conversions for each DWORD (splitting each<br />DWORD into seven 5 bit fields and then encoding each 5 bits) giving 14 characters for<br />both DWORDS, but since it would be better to treat both DWORDS as a single QWORD and<br />split the 64 bits into 13 parts saving even one more character, that method will be<br />selected. A multi-level table lookup will be used to convert the encoded 13 characters<br />back into a binary value (a column of 32 QWORD values indexed by the character value, and<br />13 columns of these QWORD values indexed by which character of the encoded value was<br />being decoded, all 13 resulting values would be accumulated by adding to yield the QWORD<br />binary value, then split to two DWORDS).<br /> <br />The size values in the first (lowest level) directory (three BYTE size values) also need<br />to be converted to character values. For small prime number size values (2, 3, 4, ...)<br />this would create character strings such as "AAAAB", and there would also be no need for<br />the High DWORD, thus such small prime numbers would be saved as only a truncated size<br />field (delete any leading 'A' characters) and would only contain a single DWORD value in<br />the next lower directory level (second level) such as:<br /> <br /> First Second<br /> Level Level<br /> <br /> "B" for 2 bits<br /> "AAAAAAB" for prime number 2<br /> "AAAAAAC" for prime number 3<br /> "C" for 3 bits<br /> "AAAAAAE" for prime number 5<br /> "AAAAAAG" for prime number 7<br /> "D" for 4 bits<br /> "AAAAAAK" for prime number 11<br /> ...<br /> ...<br /> <br />No attempt will be made to delete the leading 'A' characters in these short prime numbers.<br /> <br />When the bit size exceeds 32 bits, the second DWORD would be created to precede the first<br />DWORD in the directory name. This second (most significant) DWORD would consist of the<br />most significant 32 bits of the prime number and would always have the most significant<br />bit set (always be at least an encoded "B..."), and would result in an encoded 13<br />character directory name.<br /> <br />The max size of a prime number of 300 digits is 32 DWORDS or 16 QWORDS which would convert<br />to a directory name of 232 characters ((13 + 1) * 16) + (5 + 1) + (1 + 1)) (max directory<br />name size plus a separator times 16 sub directory levels plus size directory name plus a<br />separator plus the drive name plus a separator). This is well within the MAX_PATH for a<br />directory entry which is 260 BYTES so unicode path names are not required.<br /> <br />The factoring algorithm starts out by factoring the semi prime's lowest DWORD and highest<br />32 bits into lists of DWORD pairs (masked to a low DWORD for the low DWORD pair and to a<br />high DWORD for a high 32 bit pair) whose DWORD products match the appropriate end values<br />of the semi prime. Prime numbers whose ends match these pairs are the only prime numbers<br />that need to be considered in the factoring process, all other prime numbers cannot<br />possibly be the correct values. All four of the possibilities must be considered (one at<br />a time) when considering which value of a pair belongs to the larger prime number and<br />which value belongs to the smaller prime number. Assume that the end values for the first<br />(odd number) table pair values were A and B and the second (MSD bit set) table values were<br />C and D. The possible test primes would then be:<br /> <br /> Small and Large<br /> <br /> C ... A and D ... B<br /> C ... B and D ... A<br /> D ... A and C ... B<br /> D ... B and C ... A<br /> <br />Start the building process by creating four number buffers (bit fields) whose bit size is<br />the bit size of the semi prime extended to a mod 32 bit size. Now process each of the<br />above mentioned 4 possible pairs, let us say, starting with the C ... A and D ... B pair. <br />Multiply them as follows:<br /> <br /> C ... A<br /> * D ... B<br /> --------<br /> RS = B * A (R ignored)<br /> TU = D * C (U ignored)<br /> <br /> One word about my selection of variable names R, S, T, U, W, X, Y, and Z (in the<br /> example above and in the example below). I did not use the letter "V" because in my<br /> text editor (PFE), while using the OEM fixed pitch font, the "U" (Uniform) and "V"<br /> (Victor) letters appear almost the same and are easily confused.<br /> <br />Now, S would be equal to the lowest DWORD of the semi prime because the A and B characters<br />were entries in the factor table for the lowest DWORD in the semi prime, but R needs to be<br />calculated and saved. T would be equal to the highest 32 bits of the semi prime for the<br />same reason and U needs to be calculated. S and T will always match the end DWORDS of the<br />left shifted semi prime (also, see below). The R must be calculated as (A * B) >>= 32 and<br />T must be calculated as (C * D) >>= 32. This will be done once as the factor pair lists are<br />read and the R values and U values (1 for each pair) saved in two arrays for later use.<br /> <br />Look up the directory ".\Ss\C A" and the directory ".\Sl\D B" (where "Ss" is the small<br />test prime number size and "Sl" is the large prime number size), and the lowest of their next<br />level sub-directories (treat the sub-directories as a list of possible useful matches). If<br />either such directory or sub-directory entry does not exist, then skip to the next low or<br />high list entry and retry.<br /> <br />Access the first of the ".\Ss\C A" sub-directory entries and assume that it contains the 2<br />DWORDS as E F and that the first of the ".\Sl\D B" sub-directory entries contains the 2<br />DWORDS as G H. Combine the sub directory values with the parent directory values to<br />continue building the prime numbers as:<br /> <br /> C E ... F A<br /> * D G ... H B<br /> ------------<br /> <br />Multiply F A and H B and mask the product to a QWORD and check if the result matches the<br />least significant QWORD of the semi prime:<br /> <br /> F A<br /> * H B<br /> ----<br /> RS = B * A (already computed above)<br /> TU = B * F (T ignored)<br /> WX = H * A (W ignored)<br /> YZ = H * F (YZ ignored)<br /> ----<br /> IJKL (IJ ignored)<br /> <br />K ((R + U + X) / DWORD) should match second lowest DWORD of the semi prime. If not, select<br />the next low pair and try again,<br /> <br />Multiply C E and D G and check if the most significant 64 bits of the product matches the<br />most significant 64 bits of the semi prime:<br /> <br /> C E<br /> * D G<br /> ----<br /> RS = G * E<br /> TU = G * C<br /> WX = D * E<br /> YZ = D * C (already computed above)<br /> ----<br /> MNOP (OP ignored)<br /> <br />MNOP may possibly need to be adjusted because the product may just be 127 bits and not 128<br />bits. If and only if (IFF) the most significant two bits of C and D are both set, then the<br />product would be 128 bits, otherwise it would be 127 bits and require a shift to be<br />correct for a compare with the high semi prime value (the semi prime high end would be<br />already left shifted to set the most significant bit of a DWORD). Because of this anomoly,<br />all products starting with these pairs (for all 16 levels) must be left shifted by one<br />bit. This is time comsuming. To avoid this, the left shifted semi prime has been also<br />saved as a right shifted by one bit value. When the high factor pair is first selected, a<br />check will be made and the correct pointer to the semi prime check value will be<br />established for that pair, and product shifting will not be required.<br /> <br />M and N should match the highest 64 bits of the check semi prime. If not, select a new<br />high pair and reset the low pair to the beginning (working with a new high pair) and start<br />again until both pairs match. Note that O and P cannot be checked at this time because it<br />is unknown how much the carry DWORDS will be until the next level testing can select the<br />third DWORD pair.<br /> <br />If the end of either factor list is reached before the double match, change which of the<br />four initial pairs is being used, and if all four pairs have been checked, then change the<br />test number bit sizes (alternate lower and higher around the smaller value mid-point that<br />was selected and then recalculate the larger number bit count), and reset the lists and<br />start again until the actual factors are found.<br /> <br />If both end points match then check if you are at the lowest level. Do this by maintaining<br />the bit sizes by decrementing by 64 as you go to each next level - when the smaller test<br />number lower size is less than 64, then hold the smaller test number and just process the<br />larger test number for subsequent levels.<br /> <br />If both sizes are less than 64 then you have the final test primes. Just multiply out the<br />DWORD values (to get all middle carries) to verify whether this is a valid solution. To<br />get these values (they are split into 4 parts during this testing), the low DWORD values<br />are correct, it is only the high values that need to be adjusted and concatenated to the<br />top of the low values and then multiplied. To do this for the smaller test value, subtract<br />the bit size of the smaller test value lower test DWORDS (DWORD count * 32) from the total<br />bit size of the smaller test value. Divide the result by 32 (a shift works really well)<br />and what remains is the bit count to right shift the smaller test value high DWORD values<br />deleting low bits that are shifted out of the lowest DWORD value in the high piece (use<br />right shift double on pairs of adjacent DWORDS), then concatenate the result to the low<br />DWORDS. Do the same thing to adjust the larger test value high DWORDS. Then multiply and<br />check the product with the semi prime itself.<br /> <br />If both sizes are > 63 then drop down both of the directory levels and get the next two<br />pair of DWORDS for the test prime numbers and extend the multiplies by a DWORD each and<br />check again until you have the final test primes.<br /> <br />Obviously, quit when you find the two final prime numbers that, when multiplied, result in<br />the semi prime product.<br /> <br /><br />Dave.
http://www.codeproject.com/Messages/4791183/Factoring-algorithm.aspx
Member 4194593Tue, 01 Apr 2014 14:46:00 GMTAlgorithmsTeam Contract AlgorithmHi,<br />
<br />
I want to make a simple algorithm for F1 Challenge. Basically i want to make an external program that takes my race results and at the end of the season i get "contract offers" depending on how well i did. I already know how i want it to work, i just want to know if there's already an algorithm similar to this?
http://www.codeproject.com/Messages/4788336/Team-Contract-Algorithm.aspx
Laurence SennaFri, 28 Mar 2014 06:23:00 GMTAlgorithmsDetecting File ChangesI use Carbonite backup service on my main machine. Carbonite claims that they are able to transmit only changes in a file to their servers so that the whole file needn't be transmitted again when there are changes to that file.<br />
<br />
How are they doing this? Wouldn't they need to compare the changed file against a complete copy of the original? And to do this across the net would require transmitting the entire file anyway, right?<br />
<br />
<img src="https://dj9okeyxktdvd.cloudfront.net/script/Forums/Images/smiley_confused.gif" align="top" alt="Confused | :confused:" /> <br />
<div class="signature"><br />
<br />
<br />
The difficult we do right away...<br />
...the impossible takes slightly longer.</div>
http://www.codeproject.com/Messages/4788233/Detecting-File-Changes.aspx
Richard Andrew x64Thu, 27 Mar 2014 23:44:00 GMTAlgorithmsHow much is my encryption algorithm worth?I developed a lossless, key-based, encryption algorithm that can work in any modern programming language and it has a 1-to-1 relationship between the unencrypted values and the encrypted values as long as the key remains the same and the minimum values and maximum values are known. The key can also be of virtually limitless size or of a very limited size. The algorithm uses carefully calculated mathematics to give the appearance of gibberish until it is decoded with the proper key or combination of keys. Other than that, I cannot reveal anything, lest I lose any intellectual property right opportunities that I have to the algorithm. How much is this encryption algorithm potentially worth if I patent it?
http://www.codeproject.com/Messages/4784507/How-much-is-my-encryption-algorithm-worth.aspx
Daniel MullarkeySun, 23 Mar 2014 06:47:00 GMTAlgorithmsOptimization algorithmI wonder what optimization algorithm should be used for such a problem:<br />
x: independent variable <br />
y: dependent variable<br />
<br />
For y = f(x), find all x such that:<br />
<br />
sum of y is > p where p is a positive integer<br />
sum of y is the minimum of all sums that are greater than p
http://www.codeproject.com/Messages/4773618/Optimization-algorithm.aspx
Gordon KnotThu, 06 Mar 2014 16:15:00 GMTAlgorithmsalgorithm for proving a set of logical conditions is not self-contradictoryI have been interested in Decision Tables [<a href="http://en.wikipedia.org/wiki/Decision_table" target="_blank" title="New Window">^</a>] a long time, and lately I found myself wanting to do some exploratory programming to create a Decision Table UI, and parse it, and crank out a bunch of complex logical assertions in a form that would be useful for creating a set of "business rules," state-machines, language-parsers, etc.<br />
<br />
I suspect some of you "old-timers" here have experience with decision table software, and theory.<br />
<br />
The most interesting aspect of decision-table theory, to me, is the analysis of a set of complex logical statements to see if there are ambiguities, contradictions, or "incompleteness."<br />
<br />
I don't quite know how to conceptualize the dynamics of the process of logical verification; I'm posting this message to just ask for some pointers to any resources you are aware of for theory or algorithms useful for this.<br />
<br />
I'm not looking to find code, at this point. I have been searching on the web, and have been examining the various commercial software packages for Windows for decision tables (pricey !). Nothing yet has really given me any ideas on the theory/algorithms for logical "provability."<br />
<br />
thanks, Bill<br />
<div class="signature"><font color="blue"><small>“But I don't want to go among mad people,” Alice remarked.<br />
<br />
“Oh, you can't help that,” said the Cat: “we're all mad here. I'm mad. You're mad.”<br />
<br />
“How do you know I'm mad?” said Alice.<br />
<br />
“You must be," said the Cat, or you wouldn't have come here.” Lewis Carroll</small></font></div>
http://www.codeproject.com/Messages/4763782/algorithm-for-proving-a-set-of-logical-conditions.aspx
BillWoodruffThu, 20 Feb 2014 17:57:00 GMTAlgorithms