Cubic Equations And The Complex Field

One thing I wish to see in languages such as PHP is to find them supporting the complex type. Complex numbers are more than vectors in 2D, and I wish to see expression containing them parsed just like the ones with real numbers. Python supports them, and you have to import ‘cmath’ to use functions of a complex variable. To import cmath type

import cmath

For example, complex numbers are useful in solving cubic equations even if all its roots are real. And cubic equations can be used for Bézier curve manipulations.

Following is the Cardan formula for solving a cubic equation

Be x^3 + ax^2 + bx + c=0 a cubic equation.

Step 1

Convert the equation to the form latex y^3 + py + q = 0
Use the Taylor series formula, to find a k, such that y=x-k:
Be P(x) = x^3 + ax^2 + bx + c
Then, P(x) = P(k) + P'(k)x + {P''(k)x^2 \over 2} + {P'''(k)x^3 \over 6}
P(k) = k^3 + ak^2 + bk + c
P'(k) = 3k^2 + 2ak + b
P''(k) = 6k + 2a
P'''(k) = 6

Because P”(k)=0, 6k + 2a=0, thus:
k= - {a \over 3} .
p=P'(k) = b - {a^2 \over 3}
q=P(k) = {2a^3 \over 27}  - {ba \over 3} + c

For example,
x^3 - 7x^2 +14x - 8 = 0
will become
y^3 -2{1 \over 3}y - {20 \over 27} = 0
In Python:

a = -7
b = 14
c = -8
p = b - a**2 / 3.
q = 2*a**3 / 27. - b*a/3. - 8

Step 2

Find 2 numbers u and v that will help us solve the equation. If y=u+v , then the new equation will be:
u^3 + v^3 + (p + 3uv)(u + v) + q = 0
We can find u,v such that (p + 3uv) = 0,
Thus,

and latex u^3 + v^3 = -q
Since p+3uv=0, u^3{v^3} = {-p^3 \over 27}
From both equations, we get that latex u^3 and latex v^3 are the roots of the quadratic equations
t^2 +qt - {q^3 \over 27} = 0
The roots of the quadratic equations are:
(1) u^3 = - {q \over 2} + \sqrt{{q^2 \over 4} + {p^3 \over 27}}
(2) v^3 = - {q \over 2} - \sqrt{{q^2 \over 4} + {p^3 \over 27}}
In Python, the inner root can be computed using:

innerRoot = cmath.sqrt(q**2 / 4. + p**3/27.)

Now, u and v are cubic roots of (1) and (2) respectively. They must satisfy 3uv=-p.
In Python, you get your initial u using:

u=(-q / 2. + innerRoot) ** (1/3.)

If the pair u,v does not satisfy 3uv = -p, you can multiply your v by
$latex-1 + i \sqrt 3 \over 2 $
until the pair satisfies the condition.
Now, having a solution, get the next by multiplying u by $latex-1 + i \sqrt 3 \over 2 and v by latex-1 – i \sqrt 3 \over 2

In our example:
u^3 = {20 \over 54} + \sqrt{{-263 \over 729}}
v^3 = {20 \over 54} - \sqrt{{-263 \over 729}}

Let’s find our three solutions:
u_1= (0.8333333333333335+0.28867513459481187j), v_1=(0.8333333333333335-0.28867513459481187j)
Thus, latex $y_1 = (1.666666666666667+0j)$
u_2 = (-0.6666666666666659+0.5773502691896264j), v_2=(-0.6666666666666657-0.5773502691896264j)
Thus, y_2 = (-1.3333333333333317+0j)
u_3 = (-0.1666666666666676-0.8660254037844383j), v_3=(-0.1666666666666677+0.866025403784438j)
Thus, y_3 = (-0.3333333333333353-2.220446049250313e-16j)

(The above values are output from Python script. The real results look much better.)
Now, to get the roots of the original equation, add k={-a \over 3} to each y.
In our example,
k = 2{1 \over 3}
Thus,
x_1 = 4, x_2=1, x_3=2

Writing expressions is much easier and more readable when the language supports the complex type.

Advertisements

PHP New Major Version

When you see a change in the major version (the number before the first point of the version id), expect a great leap. New features have been added to PHP in version 7, that make programming more convenient. I’m going to discuss some of them.

Null Coalescing

Suppose you’re trying to get a value from a request, and set it to zero if not sent. So instead of typing

$val = $_GET['foo'];
if ($val == null)
  $val=0;

Simply use ?? as follows:

$val = $_GET['foo'] ?? 0;

The Spaceship Comparison Operator

When making a decision based on comparisons between to values, would you like to use a switch command instead of if ... else? Use the operator ‘<=>’ to compare numbers or strings.
$a<=>$b will return one of the following values:
* -1 if $a is smaller than $b
* 0 if $a equals $b
* 1 if $a is greater than $b

Generator Functions

Generator functions have been introduced in PHP 5.5. They allow you to elegantly use generated values in a foreachloop without calling the function time and time again.
For example, the following code:

<?php
function factUpTo($n){
  $genValue=1;
  for ($i=1; $i<=$n;$i++){
    $genValue *= $i;
    yield $genValue;
  }
}

foreach (factUpTo(8) as $j){
  print $j . "\n";
}
?>

produces the following output:

1
2
6
24
120
720
5040
40320

Following are features introduced in PHP 7:

Returned Values

In addition to generating values, a generator can return a value using the return command. This value will be retrieved by the caller using the method getReturn().

For example, the code:


<?php

$gen = (function() {
    yield 1;
    yield 2;

    return 3;
})();

foreach ($gen as $val) {
    echo $val, PHP_EOL;
}

echo $gen->getReturn(), PHP_EOL;

will produce the output:

1
2
3

Delegation

A generator function can generate values using another generator function. This can be done by adding the keyword from after the command yield.
For example, the following code:


<?php
function gen()
{
    yield 1;
    yield 2;
    yield 4;
    yield from gen2();
}

function gen2()
{
    yield 8;
    yield 16;
}

foreach (gen() as $val)
{
    echo $val, PHP_EOL;
}
?>

will produce the following output

1
2
4
8
16

Return Type Declaration

A return type can be declare by adding it at the end of the function declaration after colons.
For example:

function myFunc(): int
{
.
.
.
return $retValue;
}

returns an integer.

Why Write The Return Type At The End?

Two possible reasons to write the type at the end of the declaration and not at the beginning like in Java, C, and other c-like languages:
* In PHP, the function declaration begins with the keyword funcction. The return type is optional.
* This syntax already exists in AcrionScript.

Find more about PHP 7 in the chapter Migrating from PHP 5.6.x to PHP 7.0.x of the php.net site documentation.

Written with StackEdit.

Meltdown – The Computer Lab Prank

I remember that little prank from the days I was a student. You work on an X terminal, and out of the blue, all the display contents gradually disappear’ Pixel after pixel turns black. But don’t worry – you’ll regain control over your display shortly. shortly.
Everyone can access other X terminal display, and mess with it.

How Does It Work?

This program is a simple one using the GDK library, Gnome’s window management package. Including ‘gdk.h’ will also include:

The Program’s Flow

The main function of the program performs the following steps:
1. Initialize GDK.
2. Create a window whose dimensions are the same as those of the root window.
3. Make the window’s background transparent.
4. Make the window a full-screen window.
5. Add an event handler. to handle Expose events.
The event handler will perform the following steps:
1. Create a list of columns and lengths (number of blackened pixels).
2. Create the Graphics Context for the window.
3. Blacken pixels until all pixels are black.
4. Quit the main loop.

Includes And Structures:

#include <stdio.h>
#include <stdlib.h>  
#include <gdk/gdk.h>

GMainLoop *mainloop;
GList *list;

typedef struct col_and_length_t{
  short col;  // Column number
  short len;  // Number of blackened pixels.
} col_and_length;`

The main function:

int main(int argc, char *argv[]){
  gdk_init(NULL, NULL);
  GdkDisplay *disp=gdk_display_get_default();
  GdkScreen *scr = gdk_display_get_default_screen (disp);
  GdkWindow *root = gdk_screen_get_root_window(scr);
  int rootWidth = gdk_window_get_width(root);
  int rootHeight = gdk_window_get_height(root);
  GdkWindowAttr attr;
  attr.width=rootWidth;
  attr.height=rootHeight;
  attr.x=0;
  attr.y=0;
  attr.window_type = GDK_WINDOW_TOPLEVEL;
  attr.wclass=GDK_INPUT_OUTPUT;

  GdkWindow *newWin=gdk_window_new(root,&attr, GDK_WA_X | GDK_WA_Y);
  gdk_event_handler_set (eventFunc, newWin, NULL);
  GdkRGBA color;
  color.alpha=0;

  gdk_window_set_background_rgba(newWin, &color);
  gdk_window_fullscreen(newWin);
  gdk_event_handler_set (eventFunc, newWin, NULL);
  gdk_window_show(newWin);
  mainloop = g_main_new (TRUE);
  g_main_loop_run (mainloop);
  gdk_display_close(disp);

return 0;
}

The event handler

void start_meltdown(GdkWindow *newWin, int height){
  cairo_t *gc=gdk_cairo_create(newWin);
  cairo_set_line_width(gc,2);
  cairo_set_source_rgb (gc, 0, 0, 0);
  int cell_no,size;
  GList *link;
  col_and_length *link_data;
  size=g_list_length(list);

  while(size>0){
    cell_no=random() % size;
    link = g_list_nth(list,cell_no);
    link_data = (col_and_length *)link->data;
    cairo_move_to(gc, link_data->col, link_data->len);
    cairo_rel_line_to(gc, 0, 1);
    cairo_stroke(gc);
    link_data->len++;
    if (link_data->len >= height){
      list=g_list_remove_link(list, link);
      --size;
    }
  }
  g_main_loop_quit(mainloop);
}

void eventFunc(GdkEvent *evt, gpointer data){
  GdkWindow *newWin = (GdkWindow *)data;
  if (gdk_event_get_event_type(evt) == GDK_EXPOSE && gdk_event_get_window (evt) == newWin){
    int width=gdk_window_get_width(newWin);
    int height=gdk_window_get_height(newWin);
    int i;
    for (i=0; i<width;i++){
      col_and_length *cell=(col_and_length *)calloc(sizeof(col_and_length), 1);
      cell->col=i;
      cell->len=0;
      list = g_list_append(list, cell);
    }
    start_meltdown(newWin,height);
  }

}

Compiling

In linux, compiling a program is easy thanks to the pkg-config command.
Run the following from the command line:

gcc meltdown.c `pkg-config --cflags --libs gdk-3.0` -o meltdown

Now, to run the program type:

./meltdown

Written with StackEdit.

Rotate Your Movie

I have received by e-mail a rotated video in the ‘flv’ format. The video was supposed to be a vertical one, but it turned out to be horizontal, that is ROTATED. So, I wrote a little program to rotate it back using libming.
There are two things to take care of when processing the input FLV:

  • The video stream.
  • The sound stream.

Both can be taken from the FLV file.
The code is written in C++, but can be translated easily into PHP. Following is the code:

#include <iostream>
#include <mingpp.h>

using namespace std;

int main(){
  const char *flvFile ="/path/to/inputVideoFile.flv";

  // Get the video stream from the file. The input file can be in the FLV format.
  SWFVideoStream *stream = new SWFVideoStream(flvFile);

  SWFMovie mov (9);  // Create the movie object.

  // The method 'add' returns a display item.
  // Display items can be rotated, transformed, etc.
  SWFDisplayItem *di=mov.add(stream);  

  // Sound streams are taken from a file object. 
  FILE *soundFD = fopen(flvFile, "rb+");
  SWFSoundStream sound(soundFD);

  // The original dimensions of the video are 426 X 240.
  di->rotate(-90);  // Rotate the item 90 degrees clockwise
  di->move(240, 0);  // The rotation moves point (0,240) to (-240,0).


  mov.setSoundStream(&sound,0);  // Add the sound stream at the beginning
                                 // of the movie.

  // Show the frames one by one.
  int noFrames = stream->getNumFrames();
  for (int i=0; i<noFrames; i++)
      mov.nextFrame();

  mov.setDimension(240, 426); // The new dimensions.
  mov.save("/path/to/outputVideoFile.swf", 9);
  cerr<<"Fin\n";
  return 0;
}

This will create a real vertical movie. Don’t share it on YouTube or anywhere you cannot control your movie dimensions.

Teach Yourself D3.js

D3 is a JavaScript framework used for data visualization.
Learning how to work with D3.js is very easy. If you begin with the basics, you’ll see how easy it is to use D3, because:

  • the DOM function names are much shorter than those in the legacy DOM library.
  • the same functions are used for both setting and getting values.
  • setters return a value, so you can keep working with the same element without repeating its name.

If you already know some framework, you probably feel that there’s nothing new under the sun, which is good because it makes learning the new stuff easier.

So, What’s New?

In D3, you can:
* add and remove SVG and HTML elements using the setters and getter.
* set and get the element’s properties, attributes, styles, text and… data

Getting Started

First, download the framework from http://d3js.org
After you include it in your script, you can use selections, that is wrappers for elements.
To get a selection, use one of the functions:

  • d3.select(selector) – to select the first element matching selector.
  • d3.selectAll(selector) – to select the all elements matching selector.

Like the d3 object, selections has their select and selectAll methods to select descendant.

If selection is a selection, it’s easy to understand what selection.text(), selection.attribute(), selection.style(), selection.insert(), and selection.append() do. But, what does selection.data() do?

Data And Update Selection

The selection’s method data() helps you use the HTML DOM as a database.
selection.data() returns an array of all data that belongs to the elements of the selectionץ The data is held in the property __data__ of the element.
selection.data(arr, func) – defines an update selection and distribute the elements of array arr to the elements of selection.
func(d,i)is a function that:

  • receives d an element of arr and its index i.
  • returns a record key.

If func is not passed, the key is the element’s index.

A recommended way to create an update selection is:
var updSelection = selection1.selectAll(selector).data(arr)

Now, updSelection is a selection of existing elements whose data has been changed.
In addition, updSelection has to methods:

  • updSelection.enter() – returns place holders for elements to be created under selection1.
  • updSelection.exit()– returns elements that have lost their data, and are usually to be removed.

Using the data

The methods attr, style, property, text and data can accept a function as a value to set. The function will be called for each element of the selection’s data. And its arguments will be the array element and its index.

Now, let us see it in an example.
The following code arranges data in a donut layout::

<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-type" content="text/html; charset=utf-8">
<title>Testing Pie Chart</title>
<script type="text/javascript" src="d3.min.js"></script>

<style type="text/css">
.slice text {
font-size: 12pt;
font-family: Arial;
}
</style>
</head>
<body>
<script type="text/javascript">
var width = 300, 
    height = 300, 
    radius = 100, 
    color = d3.scale.category20c(); //builtin range of colors


// Step 1: creating a container for the donut chart, and attach raw data to it.
var vis = d3.select("body")
            .append("svg")     //create the SVG element inside the <body>
            .datum([{"label":"first", "value":20},
                    {"label":"second", "value":10},
                    {"label":"third", "value":30},
                    {"label":"fourth", "value":25}])       
            .attr({"width": width, "height": height})  
            .append("g")
            .attr("transform", "translate(" + radius + "," + radius + ")") //move the center of the pie chart from 0, 0 to r, r



// Step two: defining the accessors of the layour function. 
//           The function 'pie' will use the 'value' accessor to compute the arc's length.
var pie = d3.layout.pie() 
            .value(function(d) { return d.value; })
            .sort(function(a,b){return a.label<b.label?-1:a.label==b.label?0:1;});

// Step 3: Create the update selection. 
var updateSelection = vis.selectAll("g") 
                         .data(pie);    // This will use the function 'pie' to create arc data from the row data attached to the visualisation element.


// Step 4: Using the data in the update selection to create shape elements.
var arc = d3.svg.arc() 
            .outerRadius(radius)
            .innerRadius(radius / 2)
;
updateSelection.enter()
               .append('g')
               .attr('class','slice')
               .append("path")
               .style("fill", function(d, i) { return color(i); } ) //set the color for each slice to be chosen from the color function defined above
               .attr("d", arc);                                     // Create the arc from the arc data attached to each element.

updateSelection.append("text") 
               .attr("transform", 
                     function(d) { 
                       return "translate(" + arc.centroid(d) + ")"; 
                     })
               .attr("text-anchor", "middle")                  
               .text(function(d, i) { return d.data.label; }); 


</script>
</body>
</html> 

And following is the chart:
enter image description here

For more funcions, see the API Reference.

Bézier Curves

The Bézier curve is a popular way to draw curves in graphic editors such as GIMP and Inkscape. A curve of degree n is defined using n+1 points, where the first and last are the start and end points of the curve, respectively, and the rest are control points.
For example:
fff
The curve in the image above is a cubic Bézier curve. It has start and end points (filled with blue) and two control points (with no fill).
Each control point is attached by a straight line to a start or an end point, for a reason:

  • The control points allows the user to control the curve intuitively.
  • The straight line between the start(or end) point and its control point is tangent to the curve at the start(or end) point.

The Definition

A Bézier curve is defined as the collection of points that are the result of the function
B(t) for every t in [0,1].
A linear Bézier is simply a straight line between to points P0 and P1. The function is:
(1 – t)BP0 + tBP1

For n>1, Be P0, P1 … Pn the list of the curve’s points. Then the curve’s function is defined as
BP0P1…Pn(t) = (t – 1)BP0P1…Pn-1(t) + tBP1P2…Pn(t)

Or, in its explicit form:

(Not a very precise definition because 00 is not a number, so use the value 1 instead.)

This equation can be proved easily using the Pascal triangle.
From the explicit definition, you can see that the translation is done by adding the same coordinates to which of the curves start, end and control points.
because:
Rotations and translations are done by a transform matrix. So, if T is a transform matrix:
TBP1,P2,…Pn = BTP1,TP2,…TPn

About Tangents

Now, in a Bézier curve, BP0P1…Pn(t), The line P0 – P1 is tangent to the curve at point P0, and Pn – Pn-1 is tangent to the curve at point Pn

To prove this we’ll have to show that the derivative of a Bézier curve of degree n at the start and end points is a non-zero scalar multiplied by the difference between P1 and P0, and between Pn and Pn-1.
That scalar is n.

For n=1;
BP0,P1 = (1 – t)P0 + tP1
Let’s derive:
B’P0,P1 = -P0 + P1

Good!

Let’s assume it’s correct for n, and prove for n+1
BP0,P1…,Pn+1(t) = (1 – t)BP0,P1…,Pn(t) + tBP1,P2…,Pn+1(t)
Let’s derive:
B’P0,P1…,Pn+1(t) = -BP0,P1…,Pn(t) + (1-t)B’P0,P1…,Pn(t) + BP1,P2…,Pn+1(t) + tB’P1,P2…,Pn+1(t)

Now, to get the tangent to the curve at p0, let;s assign t=0:
B’P0,P1…,Pn+1(0) = -BP0,P1…,Pn(0) + B’P0,P1…,Pn(0) + BP1,P2…,Pn+1(0) =
= – P0 + n(P1 – P0) + P1 = (n+1)(P1 – P0)

Good!
Now, to get the tangent to the curve at p0, let;s assign t=1:
B’P0,P1…,Pn+1(1) = -BP0,P1…,Pn(1) + BP1,P2…,Pn+1(1) + B’P1,P2…,Pn+1(1) =
= – Pn + Pn+1 + n(Pn+1 – Pn) + P1 = (n+1)(Pn+1 – Pn)

QED

SVG supports Bézier curves of up to the third degree. A path consisting of such curves are good approximations of shapes provided that you have enough points.