386.86

# Mathematics *

Mother of all sciences

Show first
Rating limit
Level of difficulty

## Overview of Morris's counters

7 min
1.1K

On implementing streaming algorithms, counting of events often occurs, where an event means something like a packet arrival or a connection establishment. Since the number of events is large, the available memory can become a bottleneck: an ordinary -bit counter allows to take into account no more than events.
One way to handle a larger range of values using the same amount of memory would be approximate counting. This article provides an overview of the well-known Morris algorithm and some generalizations of it.

Another way to reduce the number of bits required for counting mass events is to use decay. We discuss such an approach here [3], and we are going to publish another blog post on this particular topic shortly.

In the beginning of this article, we analyse one straightforward probabilistic calculation algorithm and highlight its shortcomings (Section 2). Then (Section 3), we describe the algorithm proposed by Robert Morris in 1978 and indicate its most essential properties and advantages. For most non-trivial formulas and statements, the text contains our proofs, the demanding reader can find them in the inserts. In the following three sections, we outline valuable extensions of the classic algorithm: you can learn what Morris's counters and exponential decay have in common, how to improve the accuracy by sacrificing the maximum value, and how to handle weighted events efficiently.

+12

## Compilation of math functions into Linq.Expression

12 min
5K

Here I am going to cover my own approach to compilation of mathematical functions into Linq.Expression. What we are going to have implemented at the end:

1. Arithmetical operations, trigonometry, and other numerical functions

2. Boolean algebra (logic), less/greater and other operators

3. Arbitrary types as the function's input, output, and those intermediate

Hope it's going to be interesting!

+4

## What's new in AngouriMath 1.2?

5 min
1.3K
Translation

After 210 days, 600 commits, tens of debugging nights, and thousands of messages in the project chat, I finally released AngouriMath 1.2.

This is an open-source symbolic algebra library for C# and F#, maybe it is interesting for someone?

+6

## Doing «Data Science» even if you have never heard the words before

12 min
1.2K

There’s a lot of talk about machine learning nowadays. A big topic – but, for a lot of people, covered by this terrible layer of mystery. Like black magic – the chosen ones’ art, above the mere mortal for sure. One keeps hearing the words “numpy”, “pandas”, “scikit-learn” - and looking each up produces an equivalent of a three-tome work in documentation.

I’d like to shatter some of this mystery today. Let’s do some machine learning, find some patterns in our data – perhaps even make some predictions. With good old Python only – no 2-gigabyte library, and no arcane knowledge needed beforehand.

0

## Jupyter for .NET. «Like Python»

2 min
1.8K
Translation
A few months ago Microsoft announced about the creation of Jupyter for .NET. However, people are barely interested in it despite how attractive the topic is. I decided to make a LaTeX wrapper for the `Entity` class from a symbolic algebra library:

Looks awesome. Is simple. Very enjoyable. Let's see more!
+2

## Objects Representations for Machine Learning system based on Lattice Theory

5 min
1.2K

This is a fourth article in the series of works (see also first one, second one, and third one) describing Machine Learning system based on Lattice Theory named 'VKF-system'. The program uses Markov chain algorithms to generate causes of the target property through computing random subset of similarities between some subsets of training objects. This article describes bitset representations of objects to compute these similarities as bit-wise multiplications of corresponding encodings. Objects with discrete attributes require some technique from Formal Concept Analysis. The case of objects with continuous attributes asks for logistic regression, entropy-based separation of their ranges into subintervals, and a presentation corresponding to the convex envelope for subintervals those similarity is computed.

+5

## Mathematics of Machine Learning based on Lattice Theory

7 min
1.7K

This is a third article in the series of works (see also first one and second one) describing Machine Learning system based on Lattice Theory named 'VKF-system'. It uses structural (lattice theoretic) approach to representing training objects and their fragments considered to be causes of the target property. The system computes these fragments as similarities between some subsets of training objects. There exists the algebraic theory for such representations, called Formal Concept Analysis (FCA). However the system uses randomized algorithms to remove drawbacks of the unrestricted approach. The details follow…

0

## MEMS accelerometers, magnetometers and orientation angles

8 min
9.7K
Translation

When it's necessary to evaluate the orientation angles of an object you may have the question — which MEMS sensor to choose. Sensors manufacturers provide a great amount of different parameters and it may be hard to understand if the sensor fit your needs.

Brief: this article is the description of the Octave/Matlab script which allows to estimate the orientation angles evaluation errors, derived from MEMS accelerometers and magnetometers measurements. The input data for the script are datasheet parameters for the sensors. Article can be useful for those who start using MEMS sensors in their devices. You can find the project on GitHub.
+5

## Developing a symbolic-expression library with C#. Differentiation, simplification, equation solving and many more

15 min
6.5K
Hello!

[UPD from 12.06.2021: if you're looking for a symbolic algebra library, AngouriMath is actively developed. It's on Github and has a website. Discord for questions]

Why does programming a calculator seem to be a task, which every beginner undertakes? History might have the answer — computers were created for this exact purpose. Unlike the beginners, we will develop a smart calculator, which, although won't reach the complexity of SymPy, will be able to perform such algebraic operations as differentiation, simplification, and equations solving, will have built-in latex support, and have implemented features such as compilation to speed up the computations.

It will superficially tell about assembling an expression, parsing from a string, variable substitution, analytic derivative, equation numerical solving, and definite integration, rendering to LaTeX format, complex numbers, compiling functions, simplifying, expanding brackets, and blah blah blah.
For those who urgently need to clone something, repository link.

Let's do it!
+4

## How elliptic curve cryptography works in TLS 1.3

20 min
18K

In order to (somewhat) simplify the description process and tighten the volume of the article we are going to write, it is essential to make a significant remark and state the primary constraint right away — everything we are going to tell you today on the practical side of the problematics is viable only in terms of TLS 1.3. Meaning that while your ECDSA certificate would still work in TLS 1.2 if you wish it worked, providing backwards compatibility, the description of the actual handshake process, cipher suits and client-server benchmarks covers TLS 1.3 only. Of course, this does not relate to the mathematical description of algorithms behind modern encryption systems.

This article was written by neither a mathematician nor an engineer — although those helped to find a way around scary math and reviewed this article. Many thanks to Qrator Labs employees.

### (Elliptic Curve) Diffie-Hellman (Ephemeral)

The Diffie–Hellman legacy in the 21 century

Of course, this has started with neither Diffie nor Hellman. But to provide a correct timeline, we need to point out main dates and events.

There were several major personas in the development of modern cryptography. Most notably, Alan Turing and Claud Shannon both laid an incredible amount of work over the field of theory of computation and information theory as well as general cryptanalysis, and both Diffie and Hellman, are officially credited for coming up with the idea of public-key (or so-called asymmetric) cryptography (although it is known that in the UK there were made serious advances in cryptography that stayed under secrecy for a very long time), making those two gentlemen pioneers.

In what exactly?
+21

55 min
3.6K

Chapter 2.

## The Art of Designing Road Networks

#### Transport problems of a city through the eyes of a Computer Scientist

If I were recommended an article with the title “The Art of Designing Road Networks,” I would immediately ask how many road networks were built with the participation of its author. I must admit, my professional activity was far from road construction and was recently associated with the design of microprocessors where I, among other responsibilities, was engaged in the resource consumption of data switching. At that time my table stood just opposite the panoramic window which opened up a beautiful view of the long section of the Volgograd Highway and part of the Third Transport Ring with their endless traffic jams from morning to evening, from horizon to horizon. One day, I had a sudden shock of recognition: “The complexities of the data switching process that I struggle with on a chip may be similar to the difficulties the cars face as they flow through the labyrinth of road network”.
Probably, this view from the outside and the application of methods that were not traditional for the area in question gave me a chance to understand the cause of traffic jams and make recommendations on how to overcome the problem in practice.
+13

## Polygonal Mesh to B-Rep Solid Conversion: Algorithm Details and C++ Code Samples

7 min
4K
Boundary representation (B-rep) is the primary method of representing modeled objects in most geometric kernels, including our C3D Modeler kernel. The core algorithms that edit models, such as applying fillet operations, performing cutting operations, and obtaining flat projections require the precision of B-rep representations. The rapidly growing variety of 3D data in polygonal formats makes the task of model transformations from polygons into boundary representation increasingly relevant. As a result, we developed a new SDK, C3D B-Shaper, which is part of our C3D Toolkit.

+6

## How to Catch a Cat with TLA+

3 min
1.7K
Many programmers struggle when using formal methods to solve problems within their programs, as those methods, while effective, can be unreasonably complex. To understand why this happens, let’s use the model checking method to solve a relatively easy puzzle:

## Conditions

You’re in a hallway with seven doors on one side leading to seven rooms. A cat is hiding in one of these rooms. Your task is to catch the cat. Opening a door takes one step. If you guess the correct door, you catch the cat. If you do not guess the correct door, the cat runs to the next room.
+9

47 min
2.8K
+9

## Estimation of VaR and ConVaR for the stock price of the Kazakhstani company

8 min
1.4K

The last decades the world economy regularly falls into this vortex of financial crises that have affected each country. It almost led to the collapse of the existing financial system, due to this fact, experts in mathematical and economic modelling have become to use methods for controlling the losses of the asset and portfolio in the financial world (Lechner, L. A., and Ovaert, T. C. (2010). There is an increasing trend towards mathematical modelling of an economic process to predict the market behaviour and an assessment of its sustainability (ibid). Having without necessary attention to control and assess properly threats, everybody understands that it is able to trigger tremendous cost in the development of the organisation or even go bankrupt.

Value at Risk (VaR) has eventually been a regular approach to catch the risk among institutions in the finance sector and its regulator (Engle, R., and Manganelli S., 2004). The model is originally applied to estimate the loss value in the investment portfolio within a given period of time as well as at a given probability of occurrence. Besides the fact of using VaR in the financial sector, there are a lot of examples of estimation of value at risk in different area such as anticipating the medical staff to develop the healthcare resource management Zinouri, N. (2016). Despite its applied primitiveness in a real experiment, the model consists of drawbacks in evaluation, (ibid).

The goal of the report is a description of the existing VaR model including one of its upgrade versions, namely, Conditional Value at Risk (CVaR). In the next section and section 3, the evaluation algorithm and testing of the model are explained. For a vivid illustration, the expected loss is estimated on the asset of one of the Kazakhstani company trading in the financial stock exchange market in a long time period. The final sections 4 and 5 discuss and demonstrate the findings of the research work.

+13

## The Fall and Recovery of a Mold

4 min
1.4K
Software component developers tend to be far removed from the end users of the products in which their components are employed. Recently, however, we connected directly with a KOMPAS-3D MCAD user to solve an issue involving mold design. It seems that 3D models were being exported incorrectly to data exchange formats like STP, X_T, and SAT. The cause, unhappily for us, turned out to be in our С3D Modeler geometric modeling kernel. Here is how we solved the problem, quickly.

Читать дальше →
+26

## Time Series Modelling

5 min
9.1K
Tutorial
This is a short article about understanding time series and main characteristics behind that.

## Problem statement

We have time-series data with daily and weekly regularity. We want to ﬁnd the way how to model this data in an optimal way.

Читать дальше →
+18

## Kalman Filter

9 min
5.9K
Tutorial
Translation

There are a lot of different articles on Kalman filter, but it is difficult to find the one which contains an explanation, where all filtering formulas come from. I think that without understanding of that this science becomes completely non understandable. In this article I will try to explain everything in a simple way.

Kalman filter is very powerful tool for filtering of different kinds of data. The main idea behind this that one should use an information about the physical process. For example, if you are filtering data from a car’s speedometer then its inertia give you a right to treat a big speed deviation as a measuring error. Kalman filter is also interesting by the fact that in some way it is the best filter. We will discuss precisely what does it mean. In the end of the article I will show how it is possible to simplify the formulas.
+21

## How linear algebra is applied in machine learning

5 min
14K

When you study an abstract subject like linear algebra, you may wonder: why do you need all these vectors and matrices? How are you going to apply all this inversions, transpositions, eigenvector and eigenvalues for practical purposes?

Well, if you study linear algebra with the purpose of doing machine learning, this is the answer for you.

In brief, you can use linear algebra for machine learning on 3 different levels:

• application of a model to data;
• training the model;
• understanding how it works or why it does not work.