LSB-based integer factorization

Standard factorization methods use whole numbers. There is always a certain number of steps including modulo operations, but the numbers are considered from the beginning to the end, i.e. from the Most to the Least Significant Bits (LSBs).

Another approach could be derived from the simple following number puzzle (not sure a solution exists for this one):

  A B C
  *   C
  -----
1 2 3 5

It is only necessary to look at the end of the numbers, i.e. the C, to see that there is only one solution C=5. This is the raw idea: try to deduce the LSBs first, without processing the whole numbers. A recursive search would systematically look at all pairs of LSB strings:

  p = X X 0 0 1 0
* q = X X 0 1 0 0
-----------------
  n = X X 1 0 0 0 

A common transformation used by other methods is done as following: if n is the product, p and q its factors, it is always possible to set:

n = pq = (a+b)(a-b) = a²-b², or

n + b² = a²

This operation changes the problem into finding a square number , add it to n and check if the sum if also a square (). The LSBs of squares is something that can be tested as well.

In this form, the method would surely not perform very well compared to others. The idea, if even makes any sense, must be developed and optimized, e.g.:

  • The assessment of LSBs could be integrated as speed-up in in another factorization method
  • A heuristic criterion could reduce the solutions space of the recursive search
  • Using another base for the calculations (i.e. start by converting n into this base) may simplify the assessments on LSBs
  • It may be possible to replace the recursive search by the resolution of an equations system

,

1 Comment

Ideas for mobile or desktop applications

With more time, I would develop further these projects (if it inspires somebody, please let me know):

Real-time interactive physics simulation for teachers

The direct visualization of physics experiments, and the ability to play with them, increase the understanding of physics phenomenons. Covered areas could include mechanics (see Phun), optics, electromagnetism, waves, etc. In my opinion, there is a big potential for education in the simulation of the wave equation: phenomenons such as optical diffraction, meta-materials, and in general the propagation of waves in any non-linear medium could be played with.

Podcatcher with local web-page processing

Many sites do not provide any RSS feed for the media they distribute. The user needs then to browse the corresponding pages to find the wished media, what is a repetitive task that cannot be automated. The podcatcher can use some HTML/DOM/Javascript to automate the process. A dedicated script would be needed for each web-site. A community around this feature would be needed to track web-site changes (see the Greasemonkey user scripts). The biggest advantage would be the local processing of page, no need to rely on a server.

Civilization-like game with evolution of living cells

The player would be able to control a growing creature, and evolutions would increase the available functionality (e.g. photo-sensible cells would become eyes).

Picture-by-picture comics reader

On small displays, reading a comic book is difficult because the zooming level must be high to be able to read the text, and the viewing window is hence small. A program could analyze each page on-the-fly and zoom on each image automatically (meanwhile there is a similar application on iPad, but the comic pages must be prepared).

Indoor auto-mapping per video

The application would propose to capture a video along with the recording of the position of the device (e.g. a mobile phone). After processing, a floor map of the visited rooms would be displayed. The idea here would be to use the motion compensation computation hardware (available in any modern video recording device producing mp4) in order to estimate picture changes due to parallax.

Stock indicators with simulation

Working with rapidly changing financial products is a full-time job, and the use of simple alerts (e.g. based on thresholds) is not a practicable strategy. Another approach would involve the design of programmable buy/sell indicators that each user could create on line. Indicators could be tested on the current stock values before being used for real operations. The ultimate goal would be to grow a community around these indicators, allowing users to compare indicators, bring attention to the best ones (top 10 charts) and exchange information. The variables used by indicators should include the widest range of information (stock values, news, expert opinions, Fourier transform of historical values, book of order, etc).

Information system design tool

Model-based engineering methods based on UML or SysML focus often on the visual documentation of a project. The different diagrams can be created independently, and depict as many aspects of the same system, but without a common model. As a result, inconsistencies cannot be detected automatically, and the system cannot be validated or simulated. A model-based engineering tool should focus on having a running model, from which diagrams and requirements should be exported (and not vice-versa).

Virtual origami designer

The practice of origami (paper folding) is a nice occupation but diagrams are difficult to decode and learn. A tool could help the user to see an animation of given diagram steps (with zoom and rotate capabilities), and support design functions that would allow to start at any step of any existing diagram.

I feel I shouldn’t give away all these ideas but to be realistic there is a little chance that I ever attempt to realize one of them, so it is better to have them on-line for anybody interested. And well, there is nothing ground breaking here.

Leave a comment

WebGL comes

The recent release of Chrome 9 includes a built-in module for WebGL. The result is quite impressive! Have a look at these few examples (you need either Chrome 9 or a nightly build of Firefox or Safari):

Chrome WebGL Experiments

Body Browser

ibiblio examples

Shortly, WebGL is the web version of OpenGL and provides the following features:

  • Everything runs in the browser with plain text scripts (no compilation necessary)
  • Each graphic is rendered in an HTML5 canvas (seamless integration in the HTML page)
  • Computing intensive operations such as vertex transformations or texture processing are done by the WebGL module or directly the GPU (limited interactions with Javascript for higher performance)
  • The GPU is programmable in GLSL (compiling and linking controlled from Javascript)

WebGL will obviously brings a new dimension to the web, but the fact that the GPU can be very simply controlled and programmed makes it possible to deploy almost any kind of computer intensive application simply via the web browser. I would not be surprised to see the next SETI@Home based on WebGL. A massively distributed effort to compute e.g. factorization of large numbers would be an interesting project.

Leave a comment

Recursive permutations

A while ago I was looking for a method to compute permutations of a string of n elements taken from a set of k symbols. After many very complicated tries, I came to a very simple method using a recursive function. It is given hereafter in Javascript:

function calc(n, symbols, str)
{
  if(!str)
    str = ""
  if(str.length==n)
    perms.push(str);
  else
    for(var i=0;i<symbols.length;i++)
      calc(n, symbols.substr(0,i) + symbols.substr(i+1,100), str + symbols.charAt(i));
}

The variable perms is a global array. The function works with elements placed in a character string. It uses 3 parameters: n is the size of the output string, symbols is a character string containing the symbols in lexical order, str is a temporary string used for the recursion and should not be set for a normal call.

As an example, the call calc(3, "ABCD") will produce the following values in perms:

ABC, ABD, ACB, ACD, ADB, ADC,
BAC, BAD, BCA, BCD, BDA, BDC,
CAB, CAD, CBA, CBD, CDA, CDB,
DAB, DAC, DBA, DBC, DCA, DCB

This is certainly not the most optimized algorithm to compute permutations (other methods exist), but it is so simple that I wanted to share it.

Leave a comment

Wave Propagation part 3

Last time we came to a formula that can be used to compute the simulation of a one-dimensional masses-springs system, and saw that it could be interpreted as approximation of the wave equation. This introduction was intended to show that a simple model, used primarily for a numeric simulation, leads to the same properties as a continuous system. We will use the wave equation as basis in the next posts and no more discrete system, because it yields just the same results.

The general form of the wave equation in 3 dimensions is:

∂²U/∂t² = c² ∆U = c² ( ∂²U/∂x² + ∂²U/∂y² + ∂²U/∂z² )

Where c is the speed of the wave (i.e. "celerity"), the Laplacian operator and U a scalar function of x, y, z and t. In order to make the simulation more interesting while keeping it computable, let’s look at approximated formulas in two dimensions. We are looking for the computation of U(t,x,y), and assume that we can approximate the second-order derivatives by discretization using ∆x = ∆y = ∆t = 1:

∂²U/∂t² = c² ( ∂²U/∂x² + ∂²U/∂y² )

U(t+1,x,y) – 2 U(t,x,y) + U(t-1,x,y) = c² ( U(t,x+1,y) – 2 U(t,x,y) + U(t,x-1,y) + U(t,x,y+1) – 2 U(t,x,y) + U(t,x,y-1) )

U(t+1,x,y) = c² ( U(t,x+1,y) + U(t,x-1,y) + U(t,x,y+1) + U(t,x,y-1) ) + (2-4c²) U(t,x,y) – U(t-1,x,y)

An obvious simplification of the formula can be reached by assuming c = 1, but as a consequence the propagation speed is fixed hence a phenomenon involving an interface between different mediums (e.g. refraction) cannot be simulated. Furthermore, the propagation speed would be exactly the same as the discretization intervals (e.g. ∆t). The result is that the waves move of exactly one table cell per step, what may lead to unwanted effects. With this assumption, the formula becomes:

U(t+1,x,y) = U(t,x+1,y) + U(t,x-1,y) + U(t,x,y+1) + U(t,x,y-1) – 2 U(t,x,y) – U(t-1,x,y)

Graphically, the computation of this formula can be represented as following:

Now, to define the computation completely, it is necessary to clarify the behavior at the borders and the initial conditions. For the borders, the simplest approach is to keep a border of constant cells (not processed in the computation) set to 0. The resulting behavior on the borders is a reflection of all incoming waves. Because this behavior may not be wished for a particular simulation activity, algorithms have been developed to "absorb" the incoming waves on the borders, but I won’t address them in this post. Another method, simpler but increasing the computation time, is just to extend the simulated area to a such a size that reflected waves won’t reach the interesting area before the end of the simulated time.

The initial condition is another interesting topic because 2 steps are necessary. Basically, the 2 initial steps can be set to 0 for a stable start (nothing moves unless a perturbation is introduced). Any perturbation can be inserted in the computation in either one or two consecutive steps. If only one step is changed, the perturbation has no speed and will propagate equally in all directions. If two computation steps are modified, it is possible to give a direction to the introduced perturbation, under the condition that the celerity of the medium is respected.

That’s all for now regarding wave propagation. There is not a lot of information in these 3 posts, but enough to give primary ideas and to start to develop a simple simulation. Many other methods exist for calculations based on finite differences. The goal here was to just look at one that can be understood with basic mathematics. I will come back to this topic sometimes in the (maybe far) future.

, ,

Leave a comment

Wave Propagation part 2

In the first part we considered a system composed of a chain of connected springs and masses, and came to the conclusion that the vertical position of the masses is given by the solution of a system of interdependent equations.

This system of equations is of the following form, where ai is the acceleration and Ui the position of the mass at position i:

m ai = k ( Ui-1 – 2 Ui + Ui+1 )

For each step of the computation, the new state of the system must be computed using its previous states. This is a basic mechanism for any kind of numeric simulation. The remaining difficulty is the correct representation of the acceleration term, which can be transformed using a first-order approximation, e.g. the derivative of U with respect to t can be given by:

∂U(t)/∂t ≈ ( U(t+Δt) – U(t) ) / Δt

We apply this formula two times to get the second order derivative (acceleration):

²U(t)/∂t² ≈ ( U(t+2Δt) – U(t+Δt) – ( U(t+Δt) – U(t) ) ) / Δt / Δt

²U(t)/∂t² ≈ ( U(t+2Δt) – 2 U(t+Δt) + U(t) ) / Δt²

Another way to write this formula:

²U(t)/∂t² ≈ ( U(t+Δt) – 2 U(t) + U(t-Δt) ) / Δt²

At this point, it is important to understand how to achieve the practical computation. The expected result is a set of values (the Ui) evolving over the time. The time between two consecutive steps will be exactly Δt. But the approximation of the acceleration shows that the computation of a new state of the Ui depends not only on the previous state, but also on the state before the previous state (i.e. 2 states in the past due to the t-2Δt value). Practically, this means that a total of 3 states of the Ui must be kept in memory: the current state being computed plus two steps in the past.

The usage of different steps of the computation shows that we now need to clearly identify the computed values using their temporal and spatial coordinates. An obvious simplification is to set:

Δt = 1

After that, let’s use the notation Ui(t) to identify a computed value at position i and step t. We put the approximation in place of the acceleration. The resulting formula to compute the Ui(t+1) is then:

m ( Ui(t+1) – 2 Ui(t) + Ui(t-1) ) = k ( Ui-1(t) – 2 Ui(t) + Ui+1(t) )

With this formula, the computation is straightforward because there is only one term at t+1 and all other terms are given by the previous steps. It is astonishing to see the relative simplicity of the formula (a linear combination of the previous values, no special case to handle), keeping in mind that it mimics the behavior of a physical system.

This result shows a kind of symmetry between the parts on left and right: the same pattern U(n+1)-2U(n)+U(n-1) is present, with varying time index on the left hand side and varying spatial index on the right hand side. The part on the left is the approximation of a second order derivative with respect to t. So it appears natural to try to interpret the part on the right similarly.

This can be done and results in a well-known equation that can model any linear propagation phenomenon, i.e. where each propagated wave is independent of the others. This is the Wave Equation, given here in 1 dimension:

²U/t² = c² ²U/

To be continued…

, ,

Leave a comment

Wave Propagation part 1

A while ago I created a Java applet/application to play with propagation of waves in an ideal medium. The theoretical background necessary to compute this kind of simulation is documented in this series of post.

The first step is to find an algorithm that reproduces the behavior of propagation. Propagation is a very common phenomenon that can take many forms: water waves, sound, electromagnetism, vibrating string, waves on jelly, etc. Whatever the form, propagation is always based on the local change of a property of the medium (e.g. water or air) over which the propagation occur. Even if there is an apparent movement, matter is not displaced, only the local perturbation moves.

In the case of water waves, the modified property is the local level of the water surface. For sound waves, it is air pressure. For electromagnetism it is not a scalar value but a vector. In this case, each component of the vector is assumed independent of the others and behaves like a scalar property showing propagation.

A propagation is only possible if the medium is such that the local property is in a state of stable equilibrium, i.e. the induced deformation will tend to be corrected by the surrounding environment, like a spring comes back to its initial position.

A network of springs and masses is a simple, non-continuous propagation medium that can be modeled easily.

For example, in one dimension, let’s imagine a long chain of alternating masses and springs, attached to each others. Let’s assume that each mass can move only up and down, and that gravity plays no role. In this system, if a mass is moved from its initial position, the surrounding springs will tend to pull it back. But at the same time, because both ends of the springs can move, the other masses will be pulled as well, and so on.

Now let’s consider one of the masses (at position 2 on the picture), all masses have a mass of m, the springs have a stiffness of k:

Because the masses move only up and down, only the vertical components of the forces applied by the springs need to be considered. Let’s write the sum of the forces applied to the mass at position 2, where a2 is the acceleration of the mass, and Ui the vertical position of the masses:

m a2 = ∑ forces applied to mass at 2

m a2 = F12 + F32 = k ( U1 – U2 ) + k ( U3 – U2 )

m a2 = k ( U1 – 2 U2 + U3 )

Now, different things can be noted about this relation. To begin with, no real surprise, it is a differential equation (the acceleration a2 is the second-order derivative of the position U2). If the masses at positions 1 and 3 would not move (e.g. U1=U3=0), we would obtain a perfect oscillator (the mass at 2 would go up and down following a sinusoidal movement), typically represented by an equation of the form y” + K y = 0.

Back to the considered system where the masses at 1 and 3 move and all masses of the chain are interconnected via springs. Obviously the relation shows that the vertical position U2 cannot be computed without knowing U3 and U1, which in turn depend on the positions of the next masses in the chain, and so on. It turns out that any mass in the chain can be influenced by the movement of any other mass. As a result, for each step of the computation, it is not possible to solve only one local equation for one mass, but all positions must be computed.

Stay tuned for the next part.

, ,

Leave a comment

%d bloggers like this: