Vjeux

Prime number recognition is a very hard problem and yet no good enough solution has been found using classical algorithms. There are two ways to get around those limitations: find an algorithm with a better complexity or find a way to compute faster. The first one has already been researched by a large amount of people so I decided to give a shot to the second one.

We are limited by the speed of the electricity, so my idea is to use speed of light to improve speed by a great factor. I've come up with a simple example of how to use it to compute prime numbers.

We set up 2 mirrors with light sources that are directed.

We first set the sensor to the position lower 2

2 had no light so we create a new one that is going to en-light all the multiples of 2

3 had no light so we create a new one that is going to en-light all the multiples of 3

4 is already in the light, we skip it

hasLight(n):
// Sensor placed at lower n that tells weither if it is enlightened or not
 
newLight(n):
// Creates a light that starts from lower n, targeted at the upper n + n/2,
// that first reflects to lower 2n and then to all the multiples of n.
 
isPrime(n):
for i = 2 to sqrt(n)
  if not hasLight(i)
    newLight(i)
 
return not hasLight(n)

This method allows us to recognize prime numbers with light sources, mirrors, sensors and a bit of programming.

Recognizing if a number is prime or not requires to have a lot of lasers and sensors. I don't think that is a viable process, however this could be interesting to do multiplications. You want to fire 2 lights and then see in what point they cross. However there are 2 main problems:

• It requires to have 2 really long mirrors possibly infinite which is not possible in practice. It may be possible to add a vertical mirror in order to work in a bounded area. Yet to know how many times the light hit that mirror.
• We are required either to have an infinite number of sensors. We could have only one sensor that checks all positions sequentially but then we loose the speed of light! What is wanted instead are mirrors in each position that would redirect light to a unique sensor capable of knowing where it came from.

This is an experiment and it is not at the moment near to be faster than actual methods but this is a new way to think about programming. I don't know if anything useful is going to be deviated from this but it shows how to use the light to compute things.

In SQL, this is a common issue to query the previous and next entries of the database. In order to achieve this, we are going to use a table that is sorted by the `id` field. To get the previous, the technique consists in sorting all the fields that are lower that the current one and taking the first one.

SELECT *
FROM `table`
WHERE `id` < $current_id
ORDER BY `id` DESC
LIMIT 1

Let's take an example with the values [8, 3, 4, 9, 6, 1]. We want to get the previous of 8.

• WHERE `id` < $current_id
  We first take all the values strictly lower than 8
  Result: [3, 4, 1, 6]
• ORDER BY `id` DESC
  We then sort them in descending order
  Result: [6, 4, 3, 1]
• LIMIT 1
  We take the first one
  Result: 6

You can apply the same method for the next entry:

SELECT *
FROM `table`
WHERE `id` > $current_id
ORDER BY `id` ASC
LIMIT 1

Working on the World of Raids Recruitment Tool we wanted automatic saving while editing. There are basically two ways of handling the problem.

• Send update everytime something changes. The main advantage of this technique is that you are always up to date. However, it is spamming the server on fields that are constantly being updated (text fields for example).
• Send update every X seconds. There is no longer query spike but there are two main disadvantages.

  The delay the data are sent after a modification can vary from nothing to the timer length for no apparent reason. This is a really bad feeling for the user. He will think that the application is buggy.

  The application is going to send queries all the time, even if there are no changes. We can safely assume that people are interacting a lot less than viewing so this is a real waste of resources.

We are interested in the first one, we want instant update but removing the ability to send too much data at once. What we want is to send data right after the user is done typing instead of everytime a character is typed. There is an easy way to do it in Javascript.

When you type the first character, it will start a timer of let say 100ms. Then everytime you type another character it resets the timer to 100ms. When it triggers, it will send data to the server.

This way, data will only be sent when the user interacts and with no risk of spamming the server.

var Object = {
  /* Object Code ... */
 
  timer: null,
  sendChanges: function() {
    if (this.timer) {
      clearTimeout(timer);
      this.timer = null;
    }
 
    this.timer = setTimeout(
      function () { /* Send Changes */ },
      200 /* Timeout in ms */
    );
  }
};

It has been one month that the third year (called Ing1) of EPITA started and this is a recap of the interesting projects that I developed.

malloc (1 week)
The goal of this mini-project is to improve our knowledge of memory management by implementing the C standard library memory allocator (malloc, free, realloc). Implementation using the Binary Buddy technique:

• List of free blocks of size 2^k.
• Split and Merge using adjacent block of the same size called buddy.
• Insertion and Deletion in O(log n).
• 32 & 64 bit ready.

find (1 week)
find is a very well known UNIX command used to satisfy research upon files and directories.

• File listing and options parsing with error handling.
• -name: Filtering using globbing.
• -newer, -atime, -size, -inum, -type, -links: Filtering off information sources. Handles -/+ for "less/more than".
• -perm: Filtering based on permission expressed in octal (0777) or symbolic (u+rwx,go=r) notation.

fnmatch (10 hours)
fnmatch is a function that implements globbing. It returns whether the string matches the pattern. This is mainly used to filter out files (eg: *.txt) or text search in databases (eg: LIKE '%Text%').

• *: any character 0 or more times.
• ?: any character 1 time.
• [abcA-Z]: any character from the class.
• \*: escaping.

Libstream (10 hours)
I/O functions are slow hence they should be called few time as possible. This is why they are typically buffered. The project is to recode all the I/O buffered functions of the C standard library as they are defined by the Single UNIX Specifications V3.

• fopen, fclose, fgetc, fputc, fflush: Core functions to handle buffered I/O at a character level.
• fseek, ftell, frewind: File positioning functions.
• fread, fwrite, fgets, fputs, fgetdelim: Helper functions to use buffered I/O at a string level.
• tinyPrintf: Basic string formatting (%d, %u, %s, %c, %o, %x without modifiers).

Comparison

In Javascript there are 3 types we are often comparing: String, Number and Boolean. After digging through the ECMA-262 specifications, here is the behaviour of the == operator (11.9.3) on these types:

• Number == String
  Typecasted as follow: Number == Number(String)
• Number == Boolean
  Typecasted as follow: Number == Number(Boolean)
• String == Boolean
  Typecasted as follow: Number(String) == Number(Boolean)

This means that when comparing data of two different types, they will first be converted to Number.

Note: The order of the equality is not important: A == B is the same as B == A (except the order of evalution of A and B).

You can force comparison of a and b with the type you want:

• String: "" + a == "" + b
• Number: +a == +b
• Integer: a | 0 == b | 0
• Boolean: !!a == !!b

Addition / Concatenation

The binary + operator follows a simple rule (11.6.1):

• if one of the operands is a String, both operands are converted to String and the + is a concatenation.
• Else, both operands are converted to Number and the + is an addition.

Note: Some Objects are considered as Strings like Arrays. See 8.6.2 for more informations.

Note: The operator is binary so 1 + 1 + 'a' will be executed as (1 + 1) + 'a' and therefore be equal to "2a" and not "11a".