Fear of the number 666, i.e. the number of the beast.
Just a little example of what you can accomplish in D with compile-time reflection and compile-time function execution (CTFE)
I was searching for websites with job postings, like Monster or CareerBuilder, I came across one called Dice which I decided to give a try. When I signed up, I used my personal email. I have a different email which I use for work and school which I wanted to switch to. It was simple enough:
- Login to your account
- Open up User settings
- Type in a new email address
- Click Apply
You don’t have to type in your password and there’s no confirmation email; the change is made immediately. You may already see where I’m going with this.
Changing the password requires one to type in your old password. However, resetting the password only requires one to click a verification link sent to the email associated with the account.
Furthermore, the login is the email address associated with the account.
Put it all together, all somebody needs is access to your account (left an open session on a public PC or a hacker obtained a cookie off your PC). Then they can change your email address and reset the password. The user never receives any kind of confirmation email. So any tech-savvy person can easily (and stealthily) hijack your account. Even worse, because the email address has changed, your login has changed as well. To a novice user, it may appear that their account has simply disappeared. A more savvy user may have figured out their account was hijacked, but there’s no simple procedure for recovering an account. So one would have to contact tech support and possibly wait a day or more to recover their account.
Dumb security at its finest. Given the blunders that have fallen services like LinkedIn, you’d think other major web services would have caught on by now and tightened security. Unfortunately, that is not the case.
I discovered equations in Microsoft Word so I decided to make something interesting with it.
It’s possible to devise the quadratic formula algebraically, but it’s not immediately obvious how (You must write the left side in such a form that it can be factored by “competing the square”). It’s much easier to take the final formula and work backwards.
My post on Neowin listing some of my favorite apps for Android.
XSort is an ongoing project of mine which implements a number of sorting algorithms in the D programming language. The Timsort module was implemented (with some minor revisions) in Phobos to replace the old stable sort. I’m writing this post to detail what future plans I have for the project. Items in bold are high priority. Items in italics are unofficial, meaning I’m considering them and I may or may not follow through on those plans.
- Enhance unstable sort in Phobos
- Implement Three-Pivot Quick Sort (see details below)
- Implement stable partition3 / topN functions (see details below)
- Implement smoothsort
- Implement concurrent comb sort
- Migrate “stable sort” module to merge sort
- Migrate “unstable sort” and “stable quick sort” modules to single “quick sort” module
- Write detailed documentation in modules which can be generated using DDoc
- Group all modules under an “xsort” package
- Add attributes (e.g. @stable @unstable)
Three-Pivot Quick Sort
I’m considering this as a possible candidate and contender for the unstable sort in Phobos. A person in the D forums suggested a two-pivot quick sort which I originally thought would increase the number of comparisons. I realized I was incorrect because, when utilizing multiple pivots, it would result in smaller partitions which would balance out the number of comparisons on an average case. However, I’m considering a three-pivot quick sort instead. When utilizing two pivots, each element will be compared against one or both pivots, which may result in unbalanced cases. With three pivots, each element will always be compared against two pivots resulting in more consistent behavior.
Originally, I was planning on using a median-of-five to choose the three pivots. But then I realized that utilizing three pivots makes practical new possibilities, such as sorting multiple elements, or even a median-of-medians. But more importantly, I don’t want to add unnecessary overhead and previous experience simply using a median-of-five have found it to produce satisfactory results. If evaluating more than five elements, the pivots would be chosen in this style:
1 2 3 4 5
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10 11 12 13
the first and last elements are considered to be min/max elements
Stable partition3 / topN Functions
These functions in Phobos, partition3 and topN, are currently lacking stable implementations, so I’d like to provide implementations for these as well. I’ve already implemented a stable partition3 in my stable quick sort module (link), so no problem there. However, implementing a stable topN is a much greater challenge, especially if your goal includes less than O(n) space complexity.
Currently, the unstable topN implementation works by recursively partitioning the list in-place until the nth element is discovered. This means the original order of elements is lost, including elements equal to the nth element may end up in the wrong partition.
Perhaps what constitutes a stable topN is not well defined. For me, the most important quality of a stable topN is that the original order of all elements is retained, including elements equal to the nth element. Plus, there may be two desired outcomes:
- The nth element is placed in the nth position
- The nth element remains in its original position relative to all other elements
The first outcome matches the definition of topN, whereas the second definition means to partition the list into two using the nth element as the pivot. In either case, the challenge is in finding the nth element without losing the original order of elements, which is further complicated by cases where other elements are equal to the nth element. If you can find the nth element without any reordering, than partitioning the list into two is a piece of cake.
I’ve been learning Calculus recently which has revitalized my interest in Mathematics. I found myself looking for a challenge, and so I decided to write some simple functions which will calculate popular mathematical constants. So far, I’ve written functions for calculating pi, e, and phi (golden ratio). There are various methods for calculating these constants using series or limits. However, I’m working with 80-bit precision, so I had to choose an ideal formula to obtain the max precision. Basically, numbers can’t be allowed to become too large or too small.
After an initial implementation, I worked on improving the code, which included increasing precision, optimizing, or simplifying the code. Because all of these constants are infinite sequences, you can only calculate to a specific precision, which I defined as number of rounds.
All examples are written on D and posted on DPaste so that you can see the actual results (or fork and play with the code yourself).
First up is pi: http://dpaste.dzfl.pl/ac33a0790
The only optimization I could devise is replacing (-1)^n with a conditional.
Second is e: http://dpaste.dzfl.pl/b5604425
This is a rather simple formula which I was surprised by how much it can be simplified in code. The first problem to tackle was the factorial. Even a small k could result in a very large number which is a problem for precision. Instead, (1/k!) is expanded to (1/1)(1/2)(1/3)(1/4) … which could be further optimized by remembering the product of the previous iteration. This resulted in (product *= 1/k), which could be further simplified to (product /= k).
Finally is phi (golden ratio): http://dpaste.dzfl.pl/5b8af89c
This series was more challenging to simplify, but mostly thanks to CAS (computer algebra systems), I discovered that the polynomials could be simplified by factoring. But after implementing it as a series, I discovered that the golden ratio has the very simple formula, (1 + sqrt(5))/2.