Latest Posts

New: BigIntegers

I wrote a new implementation of BigIntegers for Delphi. It uses assembler for the low level stuff, although there is a PUREPASCAL version for each of these routines too. Instead of using the GPL-licensed GNU Multi-Precision (GMP) library, I wrote everything from scratch, without using any code from others.

I think it is pretty fast, especially because I optimized many of the routines, either by techniques like loop unrolling or using 64 bits at once, or by using bitwise tricks, or by high-level algorithms like Burnikel-Ziegler, Karatsuba, Toom-Cook 3-way, etc. Results are checked with results generated by .NET. The C# test program is included.

In the course of writing this, I read an enormous numbers of publications on these subjects and I learned a lot, not only about the maths involved, but also about many other mathematical notions. Not so easy for a dentist. I also had some good help on StackOverflow.

Go take a look at my website. I think every Delphi should have BigIntegers.

posted @ Thu, 19 Nov 2015 11:29:41 +0000 by Rudy Velthuis

Rudy’s Delphi Corner is back online

Because of problems with my old domain and my provider, my old Delphi Corner website was offline for a while, and parked as subdirectory of another domain of mine.

I am very pleased to announce that it is back online, at the old address:


posted @ Sun, 15 Nov 2015 01:07:50 +0000 by Rudy Velthuis

F# Presentations at CodeMash 2016

I’ve been scouring the CodeMash accepted session list for talks featuring F#, and there are quite a few!

Bonus! Other talks of possible interest to functional programmers:

Double-Bonus! Interesting looking Pre-Compiler:

Triple-Bonus! Employment offer:

Improving is hiring developers and talented QAs in the Columbus area. It’s a nice place to work. We do interesting stuff. If that sounds good to you, talk to me! We don’t have remote positions at this time, but I’m trying to make that happen. Stay tuned!

posted @ Mon, 09 Nov 2015 20:41:59 +0000 by Craig Stuntz

Speed problems caused by code that never ran

Let me start out by telling you that I am currently implementing a (simple) BigInteger implementation for Delphi. This implementation tries to be compatible with the BigIntegers as used in .NET, so I can test my results to be the same as the results of my tests in C#.

For this, RightShift must use two’s complement semantics, and shifting a negative integer must shift in 1-bits from the top, so -100 ($FFFFFF9C) shifts to -50 (hex $FFFFFFCE). For normal Integer values, the result in Delphi would be 2147483598 (hex $7FFFFFCE), because Delphi does a simple shift and does not preserve the sign bit. But my BigIntegers should, because most other Biginteger implementations (including the .NET one, my reference) do that too.

To achieve this, in my routine, I did something like this:

class operator BigInteger.RightShift(const Value: BigInteger; Shift: Integer): BigInteger;
  LSize: Integer;
  ShiftOffset: Integer;
  RSize: Integer;
  P: PLimb;
  if Value.IsZero then

  if Value.IsPositive then
    // Call internal methods that allocate the result, shift the value right, etc.
    // Works fine, no problem.
    // Recursive call
    Result := MinusOne - ((MinusOne - Value) shr Shift);

That gave me the right results, so I was happy until I started benchmarking the new routine. I noticed that the right shift was more than twice as slow as the corresponding left shift. I did not understand this, because a right shift actually has to move fewer bits and the result is smaller. Even if I only passed in positive values, it would still be slow. The code was almost the same as the code for left shift, though. Well, except for the else clause.

People cleverer than I am probably already see the problem: the "negative" branch (the else clause) of the if clause. When I removed it, code was indeed faster than that for left shifts. But when I put it back in, even though it would never run, it slowed down everything. Only after some hard thinking and some debugging I noticed, in the CPU view, that there were calls to InitializeArray and FinalizeArray in the compiled routine, and that everything was surrounded by a try-finally block. The expression in the "negative" branch had some intermediate results, and records for these were allocated and managed by the runtime. That made the entire code slow.

First solution

My first solution was to put the code for the "negative" branch into a nested procedure of its own. The hidden local BigIntegers were now confined in that procedure and would not cause the entire routine to be slow. The "positive" part was indeed up to speed now.

I finally deconstructed Result := MinusOne - ((MinusOne - Value) shr Shift); into internal calls entirely, so no hidden BigIntegers were allocated anymore. Now I could put the "negative" code back from the nested procedure to the negative branch, and it was quite a bit faster as well.


I learned two things from this:

  • Beware of hidden code. Here, it was caused by the expression with intermediate results.
  • Inline with caution. If I had inlined the nested routine, the hidden BigIntegers would be put back in the outer scope, and things would have been slow again.

posted @ Sun, 04 Oct 2015 14:13:06 +0000 by Rudy Velthuis

Speaking at Dog Food Conference, CloudDevelop, and CodeMash

I’ll be speaking about compilers, testing, and machine learning at a conference near you! Abstracts for all of these sessions are on my Presentations page.

  • Programs that Write Programs: How Compilers Work Dog Food Conference and CodeMash
  • What Testing Can Never Do and How to Do It Anyway Dog Food Conference
  • Machine Learning with Azure ML CloudDevelop

posted @ Wed, 30 Sep 2015 13:47:37 +0000 by Craig Stuntz

Delphi Corner new URL

Because of problems with my old domain and my provider, my old Delphi Corner website is now in the hands of a domain grabber who asks a horrendous amount of money for the page.

Until I get this cleared up (if at all), I parked my pages at .

You can find the articles and components and other pieces of software there.

posted @ Thu, 10 Sep 2015 20:46:44 +0000 by Rudy Velthuis

Adding a [FixedLength] Attribute in Code-First Entity Framework

In Code First Entity Framework models, you can define the length of a string field with StringLengthAttribute, but you have to write code in OnModelCreating to indicate a CHAR/NCHAR fixed length field:

public class MyEntity
	public int Id { get; set; }

	public string FixedLengthColumn { get; set; }

public partial class MyContext : DbContext
	public virtual DbSet MyEntities { get; set; }

	protected override void OnModelCreating(DbModelBuilder modelBuilder)
		if (modelBuilder == null) throw new ArgumentNullException("modelBuilder");

			.Property(e => e.FixedLengthColumn)

I find it a bit confusing to split configuration like this, especially with a real model containing lots of fields and not this trivial example. Fortunately, you can fix it! Add these:

/// <summary>
/// Used to mark entity properties that are fixed length strings (CHAR(n) DB fields).
/// </summary>
[AttributeUsage(AttributeTargets.Property | AttributeTargets.Field, AllowMultiple = false, Inherited = true)]
public sealed class FixedLengthAttribute : Attribute {}

public class FixedLengthAttributeConvention :  PrimitivePropertyAttributeConfigurationConvention
	public override void Apply(ConventionPrimitivePropertyConfiguration configuration, FixedLengthAttribute attribute)

And change the model configuration to:

public class MyEntity
	public int Id { get; set; }

	public string FixedLengthColumn { get; set; }

public partial class MyContext : DbContext
	public virtual DbSet MyEntities { get; set; }

	protected override void OnModelCreating(DbModelBuilder modelBuilder)
		if (modelBuilder == null) throw new ArgumentNullException("modelBuilder");


posted @ Mon, 17 Aug 2015 18:26:27 +0000 by Craig Stuntz

How To Use Real Computer Science in Your Day Job

I’ll be speaking at Lambda Jam next week. Here’s the synopsis:

When you leave Lambda Jam and return to work, do you expect to apply what you’ve learned here to hard problems, or is there just never time or permission to venture outside of fixing “undefined is not a function" in JavaScript? Many of us do use functional languages, machine learning, proof assistants, parsing, and formal methods in our day jobs, and employment by a CS research department is not a prerequisite. As a consultant who wants to choose the most effective tool for the job and keep my customers happy in the process, I’ve developed a structured approach to finding ways to use the tools of the future (plus a few from the 70s!) in the enterprises of today. I’ll share that with you and examine research into the use of formal methods in other companies. I hope you will leave the talk excited about your job!

For Columbus friends who can’t make it to Chicago, I’ll be rehearsing the presentation this coming Saturday at 3.

posted @ Thu, 09 Jul 2015 19:20:54 +0000 by Craig Stuntz

Provable Optimization with Microsoft Z3

A few months ago, some coworkers sent around a Ruby challenge. It appears simple, but we can sometimes learn a lot from simple problems.

Write a Ruby program that determines the smallest three digit number such that when said number is divided by the sum of its digits the answer is 20.

In case that’s not clear, let’s pick a number, say, 123. The sum of the digits of 123 is 6, and 123/6 = 20.5, so 123 is not a solution. What is?

Here’s some Ruby code I wrote to solve it:

def digitSum(num, base = 10)
    num.to_s(base).split(//).inject {|z, x| z + x.to_i(base)}

def solution
    (100..999).step(20).reject {|n| n / digitSum(n) != 20 }.first

puts solution

Problem solved, right?

Well, no. For starters, it doesn’t even execute. There’s a really subtle type error in this code. You probably have to be fairly good with Ruby to figure out why without actually running it. Even when fixed, the cognitive overhead for understanding the code to even a simple problem is very high! It doesn’t look like the problem specification at all.

Does this version, when the bug is fixed, actually produce a correct answer to the problem? Does it even produce an incorrect solution? It’s not quite clear.

So maybe my solution isn’t so good. But one of my colleagues had an interesting solution:

def the_solution

Well, that looks really, really efficient, and it typechecks. But is it the correct answer? Will you know, six months down the road, what question it’s even trying to answer? Tests would help, but the word "smallest" in the problem turns out to be tricky to test well. Do you want methods like this in code you maintain?

The Best of Both Worlds

Is there a solution which is as efficient as just returning 180 but which also proves that 180 is, in fact, the correct solution to the problem? Let’s encode the specification for the problem in a pure specification language, SMT-LIB:

(define-fun matches-problem ((n Int)) Bool
    (>= n 100)
    (< n 1000)                   ; three digits
    (= 20.0 (/ n (digit-sum n)))))

Z3/SMT-LIB doesn’t ship with a digit-sum function, so I had to write that. You can find that code in the full solution, below.

That’s most of the problem, but not quite all. We also have to show that this is the smallest solution. So let’s also assert that there exists a "smallest" solution, which means that any other solution is larger:

(declare-const num Int)
    (matches-problem num) ; "num" is a solution
    (forall ((other Int))
        (implies (matches-problem other) (>= other num))) ; any "other" solution is larger

Now let’s ask Z3 if this specification even makes sense, and if it could be reduced into something more efficient:


And Z3 replies…

  (define-fun num () Int

A round of applause for the theorem prover, please! To see the full solution, try it yourself without installing anything.

One interesting point here: The output language is SMT-LIB, just like the input language. The "compile" transforms a provably consistent and more obviously correct specification into an more efficient representation of the answer in the same language as the input. This is especially useful for problems which do not have a single answer. Z3 can return a function matching a specification as easily as it can return an integer.

What does it mean when I ask "if this specification even makes sense?" Well, let’s say I don’t like the number 180. I can exclude it with an additional assert:

(assert (> num 180))

This time, when I check-sat, Z3 replies unsat, meaning the model is not satisfiable, which means there’s definitely no solution. So 180 is not only the smallest solution to the original problem, it turns out to be the unique solution.

Formal methods can show that your problem specifications are consistent and that your implementation is correct, and they can also guarantee that "extreme" optimizations are correct. This turns out to be really useful in real-world problems [PDF].

posted @ Fri, 06 Mar 2015 04:55:20 +0000 by Craig Stuntz

What Is the Name of This Function?

There is a function I need. I know how to write it, but I don’t know if it has a standard name (like map, fold, etc.). It takes one argument — a list of something — and returns a list of 2-tuples of equal length. Each tuple contains one item from the list and the list without that item. It’s probably easiest if I show you an example:

> f [1; 2; 3];;
val it : (int * int list) list = [
    (1, [2; 3])
    (2, [1; 3])
    (3, [1; 2])

Here’s the implementation I’m using:

let f (items : 'T list) =
    let rec implementation (start : 'T list) = function
        | [] -> []
        | item :: tail -> (item, start @ tail) :: implementation (start @ [ item ]) tail
    implementation [] items

Anybody know a standard name for this function?


In case you’re curious, the reason I want this is I’m implementing a decision tree. I have a list of functions which are predicates over the domain of my example data. I need to try each function in the list, pick the "best", and then recurse over the rest of the functions. "Best" is usually measured in terms of information gain.

It’s never a great idea to do equality comparisons on functions, so it’s helpful to transform this list into a list of functions paired with the remaining functions.

posted @ Tue, 11 Nov 2014 19:33:28 +0000 by Craig Stuntz

Server Response from: BLOGS1

Copyright© 1994 - 2013 Embarcadero Technologies, Inc. All rights reserved. Contact Us   Legal Notices   Privacy Policy   Report Software Piracy