text:
# Questions tagged [computer-architecture]

Questions about the organization and design of computer hardware.

820 questions
Filter by
Sorted by
Tagged with
23 views

### A question about Pipeline Cycle

This is my question, I am so confused with my answer, looking for help! This is my answer: However, the instructor said that if an instruction is waiting before ID, the next instruction of IF phase ...
16 views

### Help with computer engineering problem

Have been trying to figure out this problem for quite some time but don't know how to approach it. Consider a system that can host 64 GB of memory and has 8MB of L3 cache. Suppose that each cacheline ...
15 views

### how worst fit better than best fit?

I am a beginner. I have recently started studying OS. In textbook, it is written as best fit is worse than worst fit. Reason - external fragmentation. IMO,in case of variable partionioning, best ...
25 views

### doubt in pipelining

I am not from cse but trying to learn computer architecture on my own. Please clarify the following. In case of pipelining, each stage or subcomponent or subtask is assumed to be done in 1 CPU ...
12 views

### Adding two 4 bit binary numbers into 2 7 Segment LED up to 30 [closed]

I am trying to build a 2 bit binary adder into 2 7 segment LED's up to 30 and I'm having trouble getting passed nine as I believe there need to be an overflow but I am not sure. Was hoping to get some ...
17 views

### Associative mapped cache, word addressable

I have an associative mapped cache with 10 tag bits and an offset of 7bits. What is the size of each main memory block in words(word addressable) and main memory size in words? i worked it out as: ...
43 views

### What is the difference between a microoperation, microinstruction and control word?

I've seen a few lectures interchangeably use the two words (microinstruction and microoperation). I've found a source that explains the difference between a microoperation and microinstruction, but I ...
8 views

### Study of cache behaviour of algorithms on Virtualbox

I want to study certain cache oblivious algorithms and cache behaviour of some other algorithms I wrote in general. I want to understand, is it advisable, if I do this study in an virtualized ...
9 views

### Are there any models of operating systems which don't require rings of privileges, that are also secure?

I am working on a simple operating system in JavaScript and have noticed that there are two kinds of processes: the "main" process (or "kernel" process), and all the other processes. Basically they ...
25 views

### What happens with register usage in deeply nested functions calls (in theory)?

I am far from being able to construct a meaningful test for this using godbolt or some C compilation tool. But basically I am wondering what it would look like to have deeply nested function calls, ...
31 views

### How many registers does a computer *need*?

I read about Why does a processor have 32 registers?, and others. Currently I am messing around with an OS in JavaScript, and wondering how many registers -- or more specifically, how many temporary ...
8 views

### Relationship between associativity, number of sets, block size and cache inclusion policy

I'm studying for an exam and I came across a couple of questions asking me to argue whether cache inclusion is guaranteed or not. I read Wikipedia and wikipedia claims cache inclusion is possible if ...
26 views

### How does a CPU differentiate between 1-operand instructions and 2-operand instructions?

Suppose that we have 5 different instruction categories (1 OP, 2 OP, 0 OP, branch, and sub-routine instructions), how does a CPU manage to know which category is which whenever it reads an instruction ...
19 views

### Compiler optimization which does an SMT-like optimization in software?

Say I had two functions called one after the other: ...
75 views

### Is the constant pi (not Raspberry) ever used in general computer science?

Is the constant pi (not Raspberry) ever used in general computer science? If so, how so or when is it applicable?
13 views

### What does it mean for a 16 bit processor that issues 24 bit address? [duplicate]

I was solving a problem from William Stallings' 8th edition, in the cache memory section. It was question 4.6, and is as follows: Given the following specifications for an external cache memory: ...
8 views

### Approximate cache size & cache line size from optimal tile size

I wrote a program that multiplies two $N\times N$ matrices represented as 2D arrays by tiling the matrices into subsets with variable tile size. Each matrix element is an 8-Byte integer. I tested the ...
36 views

### Little Endian vs Big Endian?

Suppose a processor uses the big endian representation and x is a 32-bit integer stored in memory starting at the memory address 1000. The memory is byte-addressable, each location holding a byte. ...
24 views

### Read and write ports in a register file?

How many read and write ports in a register file? Moreover, what is the difference between a register and a register file?
37 views

### What is memory model in computer organization?

I'm new to Computer Organization and even to this community. I didn't find anything which was simple, clear and up to the point. Any examples supporting the discussion is appreciated. I'm not looking ...
28 views

### Relation between CPU cycle and Addressing modes

Professor has given this question in exam. I am not able to find relevant reference for this question Which Addressing Modes (for x86 architecture) consumes more CPU cycle?(Consider all are special ...
29 views

### What are the smallest and biggest negative floating point numbers in IEEE 754 32 bit?

I am stuck with a question that asks for smallest and biggest negative floating point numbers in IEEE 754 32-bit (their representation and decimal numerical value from which one can approximate the ...
12 views

### What is the use of relays in Harvard mark 1 (early electromechanical computer)?

First when I came to know that Harvard mark 1 had relays I thought that the relay were used like today's transistors for the purpose of processing. But I came to know that Harvard mark 1 had 5hp ...
34 views

### Can a new company make a processor compatible with Windows and current software? [closed]

Would anyone apart from Intel and AMD ever be able to make a processor that can be used on a personal computer, or is it impossible? I believe it is due to them owning the x86 instruction set, which ...
31 views

### Is 'the bombe' technically a computer?what is technically meant to be a computer?

Some say that 'the bombe' created by Alan Turing is technically not a computer despite decrypting the codes. Why is it so? Is 'the bombe' technically a computer? First of all what is technically ...
6k views

### What is a GPU year?

I am reading papers in machine learning and they say things like, "This computation took $x$ number of GPU years". What is a GPU year? How long is that?
22 views

### pipeline processor timing charts and total cycles

There are basically 2 things i need to figure out. Timing charts Total cycles for the 3 mips instructions. How does it differ when it is branch taken and branch not taken for a "predict not taken ...
14 views

### Having trouble understanding the use of a label in Assembly

I am currently having trouble understanding what this label means in Assembly as it has no variable size with it. In the following program that declares several variables in the stack offset the ...
29 views

### How to create a register from DFF bit components?

I am a new student at computer architectures and my current task is to create a register of 4 bits. We were a working DFF and my bit component seems to work. My DFF: My bit: I tried to create the ...
44 views

### What is a sticky bit in computer architecture?

I am reading about a counter implementation in RISC Architecture. The specification reads, Sticky overflow bit is set when the counter wraps through zero. I can infer that the overflow bit is ...
40 views

### Lack of Stack Pointer Register

Suppose a processor lacks STACK Pointer Register. But, It does have STACK. Then, in my opinion, a program will still be able to call subroutines but, will be unable to return back from the subroutines....
75 views

### How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

If for-loops and function calls both boil down to jump instructions when implemented on a real machine, then how is "The Ackermann function isn't implementable with for-loops" a meaningful phrase?
40 views

### L1 Cache Missing Timing Attack

I'm trying to understand Section 3: L1 Cache Missing in the paper Cache Missing for Fun and Profit. I'm stuck on trying to figure out how the covert channel is ...
191 views

### How does the computer know whether an address contains an instruction to be executed, or data to be used in an instruction?

The question is already stated in the title.
14 views

### Compare the difference in bus transfer times

Suppose we are given a 2-byte-wide bus that supports single-byte, dual-word (same clock cycle) and burst transfers. The overhead of the single-byte or dualbyte transfer is 1 clock cycle. Now we want ...
23 views

### Doubts on Virtually Indexed,Physically tagged Cache

I tried referring a few material (videos on youtube and this link as well), but I still couldn't wrap my head around the concept. My (brief) understanding of the Virtually addressed, Physically ...
42 views

### Least Significant Bit (LSB) vs Little Endian - Are they equivalent in anyway!

For a multiple choice question: What do we call the LSB? (i)Little Endian (ii)Upper bit (iii)Big Endian (iv)Lower Bit I feel ideally none of them is a true correct choice, but my best bet was (...
46 views

### Can we represent $\sqrt{2}$ exactly even with infinite bits in mantissa [closed]

Can we represent $\sqrt{2}$ exactly even with infinite bits in mantissa in floating point notation or otherwise. We actually have to prove this is not possible. But why can't we if we have infinite ...
41 views

### Why does arithmetic left shift of negative number leads to positive number?

According to this Wikipedia article, when arithmetic left shift operation is applied to a signed number, the number is multiplied by 2. But there are certain situations where a negative number becomes ...
42 views

### Software management of TLB misses?

I'm reading an OS textbook and it was talking about TLB misses being handled by software. I'm very new to all this by the way. So there's a context switch to some kernel procedure. But surely in this ...
27 views

### Cache mapping calculation

A cache has following specifications: Block size = 16 Bytes Set size = 2 way set associative Number of sets = 128 Physical address = 23 bits, byte addressable My Questions are: 1) How many blocks ...
100 views

### AMAT using Local miss rate, global miss rate, local hit rate, global hit rate

Consider the following scenario as shown in image: I have summarized the above Memory layout in terms of Miss rates and hit rates: ...
67 views

### Can a CPU be replaced without interrupting the processes running on it?

When I need to replace the CPU of my computer, I turn it off, replace the hardware, then reboot it. But what if you need to replace the CPU (in a single CPU machine) without stopping the processes ...
58 views

### Need help understanding set-associative cache

The problem I'm trying to solve is: A set-associative cache consists of 64 lines, or slots, divided into four-line sets. Main memory contains 4K blocks of 128 words each. Show the format of main ...
55 views

### Does the Hack computer from “The Elements of Computing Systems” use Von Neumann architecture?

I'm reading "The Elements of Computing Systems" (subtitled "Building a Modern Computer from First Principles - Nand to Tetris Companion) by Noam Nisan and Shimon Schocken. Chapter 4 is about machine ...
42 views

### Regarding Amdahl's balanced system law

One of the paper titled "Rules of Thumb in Data Engineering" (Jim Gray et. el.) mentions some calculations based on Amdahl's balanced system law. Link to paper: https://www.microsoft.com/en-us/...
111 views

### Why is there no extensive Standards Body overseeing ISAs, Bitcodes, Code Representation, etc… as there is in the case of Unicode

There exist a vast array of prominent bitcode formats, each suited for their specific task: LLVM IR: This format is build around a XML like binary streams model, designed to be used as a common ...
127 views

### Create NOT gate from other gates

If we are given only one NOT gate and any number of OR and AND gates, then, can we simulate more NOT gates?


text:
If my car is stuck in a hole

1. May 5, 2012

Rock_Sniffer

if my car is stuck in a hole....

I'm just doing a taught experiment, and i want to be able to prove or not that pushing down on a car that is stuck in a hole(increasing down force) uses less work force than pushing it from the back.

edit: what i came up with is- ASSUME my car is 10kg and it takes 100N to get out of the hole, but it is only exerting 60N.
so a=6m/s^2 and it is required an extra 4m/s^2 to get out.

down force is 9.81*10=98.1N

how much more do i need to get out of the hole?

Last edited: May 5, 2012
2. May 5, 2012

Infinitum

Re: if my car is stuck in a hole....

The friction would exactly balance the force exerted by the car to get out (60N) so there would be no acceleration till it crosses the 100N mark(limiting friction)

Also, I fail to see how pushing the car downwards would help get it out of the hole. Could you please elaborate it?

3. May 5, 2012

Rock_Sniffer

Re: if my car is stuck in a hole....

down force increases friction... according to my regents physics essentials text book. oh i see we need 100n for the friction to be enough to take it out.

so what i am saying is that we need 40n pushing from the back, how much do we need to increase down force to take it out?

Down Force= 9.81m/s^2*10kg=98.1N

Last edited: May 5, 2012
4. May 5, 2012

Rock_Sniffer

Re: if my car is stuck in a hole....

okay lets simplify the question. the car can only exert 60N so lets say we need 40N to move it. (10kg)

coefficient of friction is F/W = 40/98.1= .40775

5. May 5, 2012

I like Serena

Re: if my car is stuck in a hole....

Just my 2 cents.

Usually the problem with being in a hole, is lack of traction.
The engine usually has enough power, but without traction it can't climb out.

If you increase the weight, you do indeed increase the friction.
But you also increase the weight that must be pulled out.
This tends to cancel out a bit.

Pushing from the back means that the weight is not increased, but the friction against the front of the hole is increased, which is exactly where you need the traction.
This is more effective.

Of course, it's usually easier to just sit on the part of the vehicle that's in the hole...

6. May 5, 2012

Rock_Sniffer

Re: if my car is stuck in a hole....

so what are you saying, applying force to the part thats in the hole is eaiser than pushing from the back? thats what i am trying to show mathematically.

EDIT: i was assuming the car can only exert 60N and it needs 100N to get out, so an additional
40N of force from the back or increasing the down force by X amount so that 60N from the car is sufficient.

Find X and see if it is less than 40N; hence less force than pushing from the back.

7. May 5, 2012

I like Serena

Re: if my car is stuck in a hole....

I'm going for a qualitative approach before trying to calculate anything.

If the hole is deep enough (deeper than the axis of the wheel), it's impossible to get out without pushing from the back, or up.

If it's not that deep, it may be possible to sit on it to improve traction, but pushing from the back, or up, can also work.
It depends entirely on the type of hole, the slope, and the material involved (mud or snow?).

Btw, one of the typical problems is that the other wheel starts spinning, due to the differential in the axis.
But there are tricks to handle that too.

8. May 5, 2012

Rock_Sniffer

Re: if my car is stuck in a hole....

hmmm i see. i was just trying to show if pushing from the back is less or more efficient than
increasing downforce. i guess it depends.

format: plain


text:
## Intermediate Algebra for College Students (7th Edition)

$\left\{-4, -3, -2, -1\right\}$
The negative integers that are greater than $-5$ are $-4, -3, -2, -1$. Using roster method, the set is: $\left\{-4, -3, -2, -1\right\}$


text:
# Inequality related to a bijection $x\mapsto |x|^{-2}x$

Let $$x,x'\in \mathbb{R}^d$$ with usual norm. $$$$\frac{|x-x'|}{(1+|x|)(1+|x'|)} \leq \left|\frac{x}{|x|^2}-\frac{x'}{|x'|^2}\right|$$$$ I have read this inequality, however, fail to prove. I appreciate if one can demonstrate how it follows.

## 2 Answers

We need to prove that $$\left(\frac{|x-x'|}{(1+|x|)(1+|x'|)}\right)^2 \leq \left|\frac{1}{|x|^2}x-\frac{1}{|x'|^2}x'\right|^2$$ or $$\frac{|x|^2+|x'|^2-2xx'}{(1+|x|)^2(1+|x'|)^2}\leq\frac{1}{|x|^2}+\frac{1}{|x'|^2}-\frac{2}{|x|^2|x'|^2}xx'$$ or $$(1+|x|)^2(1+|x'|)^2\geq|x|^2|x'|^2,$$ which is obvious.

\begin{align*} \left|\frac{x}{|x|^2}-\frac{y}{|y|^2}\right|^2&=\frac{1}{|x|^2}+\frac{1}{|y|^2}-2\frac{x\cdot y}{|x|^2|y|^2}\\ &=\frac{|x|^2+|y|^2-2x\cdot y}{|x|^2|y|^2}\\ &=\frac{|x-y|^2}{|x|^2|y|^2}\\ &\ge\frac{|x-y|^2}{(1+|x|)^2(1+|y|)^2} \end{align*}

• Chrystomath.Second last line, correct? – Peter Szilas Jan 28 at 9:05


text:
Notes on Spark Streaming app development

This post contains various notes from the second half of this year. It was a lot of learning trying to get a streaming model working and ready in production. We used Spark Structured Streaming, and wrote the code in Scala. Our model was stateful. Our source and sink were both Kafka.

The Spark tunable that gave me 8X speedup

There are many configuration tunables in Spark. However, if you have time for only one, set this one. It made a streaming application we run process data 8X faster. That’s 800% improvement, no code change needed!

Getting top-N elements in Spark

The documentation for pyspark top() function has this warning:

This method should only be used if the resulting array is expected to be small, as all the data is loaded into the driver’s memory.

This piqued my interest: why would you need to bring all the data to the driver, if all you need is a few top elements?

The answer is: it does not load all the data into the driver’s memory.


text:
# Polynomial $x^5 + 5x^2 +1$ is irreducible or not

Which way I can determine whether the polynomial $x^5 + 5x^2 +1$ is irreducible over $\mathbb Q$ or not?

Mod $p$ Irreducibility Test and Eisenstein's criterion not applicable here.

Which way I should proceed?

• You mean you cant use the mod P irreducibility or that you tried without success? – AHandsomeAlien Jun 29 '17 at 4:29
• Reduce modulo $2$. Show that your new polymomial has no roots in $\Bbb Z_2$ and show that your reduced polynomial can't be written as $q(x)p(x)$ where $q$ has degree $2$ and $p$ has degree $3$. – Rocket Man Jun 29 '17 at 4:31
• No. Actually I tried. But then after reducing by mod5 polynomial becomes x^5 + 1 . Then I dont know how should I check if x^5 +1 is irreducible in Z5 or not. – user458361 Jun 29 '17 at 4:32
• I second AJ Stas's advice. Reduce modulo 2. The polynomial $x^5+x^2+1$ has no zeros in $\Bbb{Z}_2$, and it is not divisible by the unique (!) quadratic irreducible either. – Jyrki Lahtonen Jun 29 '17 at 4:41
• By the way, $x^5 + 1$ is not irreducible mod $5$ because $-1$ is a root. – cat Jun 29 '17 at 7:29

Try $x=y-1$. It should help by the Eisenstein's criterion.
$7^5+5\cdot 7^2+1 = 17053$ which is a prime number. Thus the polynomial is irreducible by Cohn's irreducibility criterion.


text:
# What is 1/5 as a decimal?

## What is an equivalent fraction?

Equivalent fractions are different fractions that simplify to the same basic fraction. The equivalent fraction is obtained by multiplying the same number to the numerator and the denominator.

We use the concept of the equivalent fraction to convert the given fraction to a suitable fraction and then write it as a decimal.

Step 1: Look at the denominator of the fraction. If the number in the denominator is a factor of the numbers 10,100, 1000…… etc., then the given fraction can be converted to decimal without division.

Step 2: Find the number that has to be multiplied to the denominator to make it into any of the values with 1 followed by zeroes ( 10,100,1000,……).

Step 3: Multiply the same value to the numerator.

Step 4: The number of zeros in the denominator is the number of digits the decimal point should be moved to the left in the numerator.

We can see that 5 should be multiplied by 20 to make it 100.

$$\frac{\mathbf1}{\mathbf5}\boldsymbol=\frac{\mathbf1\boldsymbol\times\mathbf{20}}{\mathbf5\boldsymbol\times\mathbf{20}}\boldsymbol=\frac{\mathbf{20}}{\mathbf{100}}$$

As we have two zeros in the denominator, move the decimal point in the numerator by 2 digits.

$$\frac{\mathbf{20}}{\mathbf{100}}\boldsymbol=\mathbf0\boldsymbol.\mathbf{20}$$

## Remember

Here are some common terms you should be familiar with.

• In the fraction $$\frac15$$, the number 1 is the dividend (our numerator)
• The number 5 is our divisor (our denominator)

Such a topic may be interesting for you: What is 1/8 as a decimal fraction?


text:
# 3. Biharmonic equation¶

This demo is implemented in a single Python file, demo_biharmonic.py, which contains both the variational forms and the solver.

This demo illustrates how to:

• Solve a linear partial differential equation
• Use a discontinuous Galerkin method
• Solve a fourth-order differential equation

The solution for $$u$$ in this demo will look as follows:

## 3.1. Equation and problem definition¶

The biharmonic equation is a fourth-order elliptic equation. On the domain $$\Omega \subset \mathbb{R}^{d}$$, $$1 \le d \le 3$$, it reads

$\nabla^{4} u = f \quad {\rm in} \ \Omega,$

where $$\nabla^{4} \equiv \nabla^{2} \nabla^{2}$$ is the biharmonic operator and $$f$$ is a prescribed source term. To formulate a complete boundary value problem, the biharmonic equation must be complemented by suitable boundary conditions.

Multiplying the biharmonic equation by a test function and integrating by parts twice leads to a problem second-order derivatives, which would requires $$H^{2}$$ conforming (roughly $$C^{0}$$ continuous) basis functions. To solve the biharmonic equation using Lagrange finite element basis functions, the biharmonic equation can be split into two second-order equations (see the Mixed Poisson demo for a mixed method for the Poisson equation), or a variational formulation can be constructed that imposes weak continuity of normal derivatives between finite element cells. The demo uses a discontinuous Galerkin approach to impose continuity of the normal derivative weakly.

Consider a triangulation $$\mathcal{T}$$ of the domain $$\Omega$$, where the union of interior facets is denoted by $$\Gamma$$. Functions evaluated on opposite sides of a facet are indicated by the subscripts ‘$$+$$‘ and ‘$$-$$‘. Using the standard continuous Lagrange finite element space

$V_ = \left\{v \in H^{1}_{0}(\Omega): \ v \in P_{k}(K) \ \forall \ K \in \mathcal{T} \right\}$

and considering the boundary conditions

$\begin{split}u &= 0 \quad {\rm on} \ \partial\Omega \\ \nabla^{2} u &= 0 \quad {\rm on} \ \partial\Omega\end{split}$

a weak formulation of the biharmonic reads: find $$u \in V$$ such that

$\sum_{K \in \mathcal{T}} \int_{K} \nabla^{2} u \nabla^{2} v \, dx \ - \int_{\Gamma} \left<\nabla^{2} u \right> [\!\![ \nabla v ]\!\!] \, ds - \int_{\Gamma}[\!\![ \nabla u ]\!\!] \left<\nabla^{2} v \right> \, ds + \int_{\Gamma} \frac{\alpha}{h}[\!\![ \nabla u ]\!\!] [\!\![ \nabla v ]\!\!] \, ds = \int_{\Omega} vf \, dx \quad \forall \ v \in V$

where $$\left< u \right> = (1/2) (u_{+} + u_{-})$$, $$[\!\![ w ]\!\!] = w_{+} \cdot n_{+} + w_{-} \cdot n_{-}$$, $$\alpha \ge 0$$ is a penalty term and $$h$$ is a measure of the cell size. For the implementation, it is useful to identify the bilinear form

$a(u, v) = \sum_{K \in \mathcal{T}} \int_{K} \nabla^{2} u \nabla^{2} v \, dx \ - \int_{\Gamma} \left<\nabla^{2} u \right>[\!\![ \nabla v ]\!\!] \, ds - \int_{\Gamma} [\!\![ \nabla u ]\!\!] \left<\nabla^{2} v \right> \, ds + \int_{\Gamma} \frac{\alpha}{h} [\!\![ \nabla u ]\!\!] [\!\![ \nabla v ]\!\!] \, ds$

and the linear form

$L(v) = \int_{\Omega} vf \, dx$

The input parameters for this demos are defined as follows:

• $$\Omega = [0,1] \times [0,1]$$ (a unit square)
• $$\alpha = 8.0$$ (penalty parameter)
• $$f = 4.0 \pi^4\sin(\pi x)\sin(\pi y)$$ (source term)

## 3.2. Implementation¶

This demo is implemented in the demo_biharmonic.py file.

First, the dolfin module is imported:

from dolfin import *

Next, some parameters for the form compiler are set:

# Optimization options for the form compiler
parameters["form_compiler"]["cpp_optimize"] = True
parameters["form_compiler"]["optimize"] = True

A mesh is created, and a quadratic finite element function space:

# Create mesh and define function space
mesh = UnitSquareMesh(32, 32)
V = FunctionSpace(mesh, "CG", 2)

A subclass of SubDomain, DirichletBoundary is created for later defining the boundary of the domian:

# Define Dirichlet boundary
class DirichletBoundary(SubDomain):
def inside(self, x, on_boundary):
return on_boundary

A subclass of Expression, Source is created for the source term $$f$$:

class Source(Expression):
def eval(self, values, x):
values[0] = 4.0*pi**4*sin(pi*x[0])*sin(pi*x[1])

The Dirichlet boundary condition is created:

# Define boundary condition
u0 = Constant(0.0)
bc = DirichletBC(V, u0, DirichletBoundary())

On the finite element space V, trial and test functions are created:

# Define trial and test functions
u = TrialFunction(V)
v = TestFunction(V)

A function for the cell size $$h$$ is created, as is a function for the average size of cells that share a facet (h_avg). The UFL syntax ('+') and ('-') restricts a function to the ('+') and ('-') sides of a facet, respectively. The unit outward normal to cell boundaries (n) is created, as is the source term f and the penalty parameter alpha. The penalty parameters is made a Constant so that it can be changed without needing to regenerate code.

# Define normal component, mesh size and right-hand side
h = CellSize(mesh)
h_avg = (h('+') + h('-'))/2.0
n = FacetNormal(mesh)
f = Source()

# Penalty parameter
alpha = Constant(8.0)

The bilinear and linear forms are defined:

# Define bilinear form

# Define linear form
L = f*v*dx

A Function is created to store the solution and the variational problem is solved:

# Solve variational problem
u = Function(V)
solve(a == L, u, bc)

The computed solution is written to a file in VTK format and plotted to the screen.

# Save solution to file
file = File("biharmonic.pvd")
file << u

# Plot solution
plot(u, interactive=True)

## 3.3. Complete code¶

from dolfin import *

# Optimization options for the form compiler
parameters["form_compiler"]["cpp_optimize"] = True
parameters["form_compiler"]["optimize"] = True

# Create mesh and define function space
mesh = UnitSquareMesh(32, 32)
V = FunctionSpace(mesh, "CG", 2)

# Define Dirichlet boundary
class DirichletBoundary(SubDomain):
def inside(self, x, on_boundary):
return on_boundary

class Source(Expression):
def eval(self, values, x):
values[0] = 4.0*pi**4*sin(pi*x[0])*sin(pi*x[1])

# Define boundary condition
u0 = Constant(0.0)
bc = DirichletBC(V, u0, DirichletBoundary())

# Define trial and test functions
u = TrialFunction(V)
v = TestFunction(V)

# Define normal component, mesh size and right-hand side
h = CellSize(mesh)
h_avg = (h('+') + h('-'))/2.0
n = FacetNormal(mesh)
f = Source()

# Penalty parameter
alpha = Constant(8.0)

# Define bilinear form

# Define linear form
L = f*v*dx

# Solve variational problem
u = Function(V)
solve(a == L, u, bc)

# Save solution to file
file = File("biharmonic.pvd")
file << u

# Plot solution
plot(u, interactive=True)


text:
The cover for my new suspense novel has been chosen. Here’s a petit morsel of it:

The composition of this cover is simple in some ways, and complicated in others. The triangle effect, the size of the lettering and the font selection are important. So are the couleurs..

A few hints about the book (and cover):

– There’s a bit of français in this novel, but not near as much as in MAKE THAT DEUX.

– The title of the book has more than one meaning, and so do several chapter titles…

– The shades of color on the cover were difficult to decide

– One of the chapters in this book is entitled “Revelation” – I will reveal the title and full cover shortly!

Another petit morceau:


text:
## Affine Structure in Ao

In designing models, we often end up stacking transforms on top of each other.

Considering a function that rotates a 2D shape:

(define (rotate shape angle)
(let ((ca (cos angle))
(sa (sin angle)))
(lambda (x y) (shape (+ (*    ca  x) (* sa y))
(+ (* (- sa) x) (* ca y))))))

Applying this transform creates a tree structure that remaps the X and Y coordinates:

Calling it a second time makes the tree twice as deep, as the top-level X' and X' values are plugged into the bottom of the same structure again.

Here's the tree produced for X'', the twice-transformed X coordinate:

This is computationally inefficient: the tree could be flattened out into a single multiple-and-add structure that rotates by the angle a + b.

In addition, chaining these operations makes our use of interval arithmetic less accurate.

Let's say that the bounds of our shape are given by $$\left\{x, y \mid 0 \lt x \lt 1, 0 \lt y \lt 1\right\}$$

Rotating once by 45º brings the bounding box to $$\left\{x, y \mid -\sqrt 2 / 2 \lt x \lt \sqrt 2 / 2, 0 \lt y \lt \sqrt 2 \right\}$$

Rotating again by 45º scales the bounding box by $\sqrt 2$ again:

After these two rotations, our calculated bounds are much larger than the actual bounds of the shape. If we collapse the two rotations into a single operation that rotates by 90º, the resulting bounds stay tight to the original shape.

These two motivations (smaller computation trees and tigher bound tracking) push for a smarter way to represent transforms. For rotations, there's an intuitive strategy for accumulating a series of operations: just sum the angles. Can we generalize further?

Rotations are an example of an affine transformation.

A rotation about the origin is the same as multiplying by the matrix $$\left[ \begin{array}{cc} \cos a && \sin a \\ -\sin a && \cos a \end{array} \right]$$

Applying a pair of rotations to a coordinate looks like the following: $$\left[ \begin{array}{cc} \cos b && \sin b \\ -\sin b && \cos b \end{array} \right] \left[ \begin{array}{cc} \cos a && \sin a \\ -\sin a && \cos a \end{array} \right] \left[ \begin{array}{c} x \\ y \end{array} \right]$$

This structure hints at our plan: instead of grouping the operations as $$\left[ \begin{array}{cc} \cos b && \sin b \\ -\sin b && \cos b \end{array} \right] \times \left[ \begin{array}{cc} \cos a && \sin a \\ -\sin a && \cos a \end{array} \right] \left[ \begin{array}{c} x \\ y \end{array} \right]$$ we can group them as $$\left[ \begin{array}{cc} \cos b && \sin b \\ -\sin b && \cos b \end{array} \right] \left[ \begin{array}{cc} \cos a && \sin a \\ -\sin a && \cos a \end{array} \right] \times \left[ \begin{array}{c} x \\ y \end{array} \right]$$

Since all the terms in the matrix are constant, this calculation can be done in advance and applied as a single matrix to the target coordinates.

This gives us generality: rotation, translation, and scaling can all be represented as affine transforms with a 4x4 matrix.

In Ao, we introduce a new opcode, OP_AFFINE, which is guaranteed to have the following tree structure:

The initial coordinates X, Y, and Z are constructed as OP_AFFINE with appropriate coefficients (e.g. X has a as 1 and and all other constants as 0).

Then, arithmetic obeys a simple set of rules:

• Adding or subtracting two OP_AFFINE trees is done coefficient-wise
• Adding or subtracting an OP_AFFINE with a scalar accumulates in the d term
• Multiplication or division of an affine by a scalar applies to all coefficients

Each of these special-cased operations returns a new OP_AFFINE tree, so we avoid building deep trees when multiple transformations are applied.

If none of these rules apply, then we build up the arithmetic tree as usual.

So, what does this accomplish?

Consider the following recursive function, which builds up a stack of twisted cubes:

(define (stack i scale rot)
(let ((base (cube '(-1 -1 -1) '(1 1 1))))
(if (= i 0)
base
(union base
(rotate-z (move
(scale-xyz (stack (- i 1) scale rot) scale)
(list 0 0 (* 2 scale)))
rot)))))

Let's compare the tree depth with and without the affine representation:

Using the affine representation, the tree stays much smaller, which means intervals will be tighter. The slope of the affine line is one level per cube, due to the stacking of union operations; the non-affine slope is four levels per cube.


text:
You are currently offline. Some features of the site may not work correctly.

# Daentl Towsend Siegel syndrome

Known as: Familial nephrosis, hydrocephalus, thin skin, blue sclerae syndrome, Hydrocephalus blue sclera nephropathy

National Institutes of Health

## Papers overview

Semantic Scholar uses AI to extract papers important to this topic.
2018
2018
• PloS one
• 2018
• Corpus ID: 2417891
As consequences of global warming sea-ice shrinking, permafrost thawing and changes in fresh water and terrestrial material… Expand
Is this relevant?
2017
2017
• 2017
• Corpus ID: 55344821
A bstractThe α′-deformed frame-like Double Field Theory (DFT) is a T-duality and gauge invariant extension of DFT in which… Expand
Is this relevant?
2013
2013
We describe the topological behavior of typical orbits of complex quadratic polynomials {P_{\alpha}(z) = e^{2 \pi \alpha {\bf i… Expand
Is this relevant?
2012
2012
• Proceedings of the Royal Society A: Mathematical…
• 2012
• Corpus ID: 19154691
The geometric Lévy model (GLM) is a natural generalization of the geometric Brownian motion (GBM) model used in the derivation of… Expand
Is this relevant?
2011
2011
Il est connu que dans le cas des courbes hyperelliptiques la conjecture de Shafarevich peut etre rendue effective, c'est a dire… Expand
Is this relevant?
2008
2008

Is this relevant?
2003
2003
Assessment of student behavior states and contextual variables has emerged as a promising area for research and practice in the… Expand
Is this relevant?
2002
2002
Abstract. It is proved that natural necessary conditions imply the existence of infinitely many integer points at which given… Expand
Is this relevant?
1998
1998
• 1998
• Corpus ID: 10903330
Abstract. We extend the classical Siegel-Brjuno-Rüssmann linearization theorem to the resonant case by showing that under A. D… Expand
Is this relevant?
1992
1992
In 1929 Siegel proved a celebrated theorem on finiteness for integral solutions of certain diophantine equations. This theorem… Expand
Is this relevant?


text:
# Explaining a comment: Difference between a transformation of points and a transformation of coordinates

In a comment to the top answer of this question Darij Grinberg says that

the problem with the dynamical perspective is that it is way harder to grasp for algebraic/combinatorial-minded people than any formula, however complicated it is. I still don't get the difference between a transformation of points and a transformation of coordinates; for me, they're all endomorphisms of a vector space.

Since apparently I'm also an algebraic minded person - I neither can see a difference between those transformations and also view only as endomorphisms - I would very much like to know what their difference consists of (even if the difference manifests itself only on the level of intuition and not of formal mathematics).

-
I was hesitant to ask this here, instead of math.SE, since the question seems to elementary, but have finally decided to ask it here, since (1) it orginated from a question from this site and (2) if the author of the statement doesn't know the difference (although he may have been jocular when he said it) an answer to this question may also be worthwhile to other algebraists on this site. –  tanktop Jul 14 at 14:09
Let $V$ be a finite-dimensional real vector space. Choosing a basis of $V$ amounts to giving an isomorphism $\phi : \mathbb{R}^n \to V$. Changing basis amounts to hitting $\mathbb{R}^n$ with an automorphism, but transforming points amounts to hitting $V$ with an automorphism.
@tanktop: as JDH mentions in the answer you link to, one can think of an automorphism of $V$ as something which "stretches, skews, reflects or rotates" $V$, while a change of of basis leaves $V$ as it was, it only moves the basis (of course that might also be considered as something dynamic). –  Michael Bächtold Jul 14 at 19:40


text:
# gridcells.analysis.spikes - spike train analysis¶

## Classes¶

 PopulationSpikes(n, senders, times) Abstraction of a population of spikes. TorusPopulationSpikes(senders, times, sheet_size) Spikes of a population of neurons on a twisted torus. TwistedTorusSpikes(senders, times, sheet_size) Spikes arranged on twisted torus.
class gridcells.analysis.spikes.PopulationSpikes(n, senders, times)[source]

Bases: collections.abc.Sequence

Abstraction of a population of spikes.

Parameters: n : int Number of neurons in the population senders : 1D array Neuron numbers corresponding to the spikes times : 1D array Spike times. The shape of this array must be the same as for senders.
class CallableHistogram(**kw)[source]

Bases: object

Callable class that computes a histogram.

get_bin_edges()[source]

Calculate bin edges.

PopulationSpikes.avg_firing_rate(tstart, tend)[source]

Compute and average firing rate for all the neurons between ‘tstart’ and ‘tend’. Return an array of firing rates, one item for each neuron in the population.

Parameters: tstart : float (ms) Start time. tend : float (ms) End time. output : numpy array Firing rate in Hz for each neuron in the population.
PopulationSpikes.isi(n=None, reduce_fun=None)[source]

Return interspike interval of one or more neurons.

Parameters: n : None, int, or sequence Neuron numbers. If n is None, then compute ISI stats for all neurons in the population. If n is an int, compute ISIs for just neuron indexed by n. Otherwise n is expected to be a sequence of neuron indices. reduce_fun : callable or None A reduction function (callable object) that performs an operation on all the ISIs of the population. If None, nothing is done. The callable has to take one input parameter, which is the sequence of ISIs. This allows to cascade data processing without the need for duplicating spike timing data. output: list A list of outputs (depending on parameters) for each neuron, even if n is an int.
PopulationSpikes.isi_cv(n=None, win_len=None)[source]

Coefficients of variation of inter-spike intervals of one or more neurons in the population. For the description of parameters and outputs and their semantics see also ISI().

Parameters: win_len : float, list of floats, or None Specify the maximal ISI value, i.e. use windowed coefficient of variation. If None, use the whole range.
PopulationSpikes.isi_neuron(n)[source]

Compute all interspike intervals of one neuron with ID n. If the number of spikes is less than 2, returns an empty array.

Todo

Works on sorted spike trains only!

Note

If you get negative interspike intervals, you will need to sort your spike times (per each neuron).

PopulationSpikes.n

Number of neurons in the population

PopulationSpikes.raster_data(neuron_list=None)[source]

Extract the senders and corresponding spike times for a raster plot.

Todo

implement neuron_list

Parameters: neuron_list : list, optional Extract only neurons given in this list output : a tuple A pair containing (senders, times).
PopulationSpikes.sliding_firing_rate(tstart, tend, dt, win_len)[source]

Compute a sliding firing rate over the population of spikes, by taking a rectangular window of specified length.

Parameters: tstart : float Start time of the firing rate analysis. tend : float End time of the analysis dt : float Firing rate window time step win_len : float Lengths of the windowing function (rectangle) output : a tuple A pair (F, t), specifying the vector of firing rates and corresponding times. F is a 2D array of the shape (n, Ntimes), in which n is the number of neurons and Ntimes is the number of time steps. ‘t’ is a vector of times corresponding to the time windows taken.
PopulationSpikes.spike_train_difference(idx1, idx2=None, full=True, reduce_fun=None)[source]

Compute time differences between pairs of spikes of two neurons or a list of neurons.

Parameters: idx1 : int, or a sequence of ints Index of the first neuron or a list of neurons for which to compute the correlation histogram. idx2 : int, or a sequence of ints, or None Index of the second neuron or a list of indexes for the second set of spike trains. full : bool, optional Not fully implemented yet. Must be set to True. reduce_fun : callable, optional Any callable object that computes a function over an array of each spike train difference. The function must take one input argument, which will be the array of spike time differences for a pair of neurons. The output of this function will be stored instead of the default output. output : A 2D or 1D array Spike train autocorrelation histograms for all the pairs of neurons. The computation takes the following steps: If idx1 or idx2 are integers, they will be converted to a list of size 1. If idx2 is None, then the result will be a list of lists of pairs of cross-correlations between the neurons. Even if there is only one neuron. If full == True, the output will be an upper triangular matrix of all the pairs, i.e. it will exclude the duplicated. Otherwise there will be cross correlation histograms between all the pairs. if idx2 is not None, then idx1 and idx2 must be arrays of the same length, specifying the pairs to compute autocorrelation for
PopulationSpikes.spike_train_xcorr(idx1, idx2, lag_range, bins=50, **kw)[source]

Compute the spike train crosscorrelation function for all pairs of spike trains in the population.

For explanation of how idx1 and idx2 are treated, see spike_train_difference().

Parameters: idx1 : int, or a sequence of ints Index of the first neuron or a list of neurons for which to compute the correlation histogram. idx2 : int, or a sequence of ints, or None Index of the second neuron or a list of indexes for the second set of spike trains. lag_range : (lag_start, lag_end) Limits of the cross-correlation function. The bins will always be centered on the values. bins : int, optional Number of bins kw : dict Keyword arguments passed on to the numpy.histogram function output : a 2D or 1D list
PopulationSpikes.windowed(tlimits)[source]

Return population spikes restricted to tlimits.

Parameters: tlimits : a pair A tuple (tstart, tend). The spikes in the population must satisfy tstart >= t <= tend. output : PopulationSpikes instance A copy of self with only a subset of spikes, limited by the time window.
class gridcells.analysis.spikes.TorusPopulationSpikes(senders, times, sheet_size)[source]

Spikes of a population of neurons on a twisted torus.

dimensions

Dimensions of the torus (X, Y)

get_dimensions()[source]

Size of the torus.

get_x_size()[source]

Horizontal size of the torus.

get_y_size()[source]

Vertical size of the torus.

nx

Horizontal size of the torus

ny

Vertical size of the torus

population_vector(tstart, tend, dt, win_len)[source]

Compute the population vector on a torus, from the spikes present. Note that this method will have a limited functionality on a twisted torus, but can be used if the population activity translates in the X dimension only.

Parameters: tstart : float Start time of analysis tend : float End time of analysis dt : float Time step of the (rectangular) windowing function win_len : float Length of the windowing function output : tuple A pair (r, t) in which r is a 2D vector of shape (int((tend-tstart)/dt)+1), 2), corresponding to the population vector for each time step of the windowing function, and t is a vector of times, of length the first dimension of r.
sliding_firing_rate(tstart, tend, dt, win_len)[source]

Compute a sliding firing rate over the population of spikes, by taking a rectangular window of specified length. However, unlike the ancestor method (PopulationSpikes.sliding_firing_rate), return a 3D array, a succession of 2D population firing rates in time.

Parameters: tstart : float Start time of the firing rate analysis. tend : float End time of the analysis dt : float Firing rate window time step win_len : float Lengths of the windowing function (rectangle) output : a tuple A pair (F, t), specifying the vector of firing rates and corresponding times. F is a 3D array of the shape (nx, ny, Ntimes), in which nx/ny are the number of neurons in X and Y dimensions, respectively, and Ntimes is the number of time steps. ‘t’ is a vector of times corresponding to the time windows taken.
class gridcells.analysis.spikes.TwistedTorusSpikes(senders, times, sheet_size)[source]

Spikes arranged on twisted torus. The torus is twisted in the X direction.


text:
# mathr

## ray42 as a Lua package using tolua

ray42 was nice as it was, but I got fed up with having to recompile each time I wanted to render a new scene, and C++ isn't a particularly friendly scene description language. So I'm now using tolua to make a Lua package from the core of ray42, and it seems to work ok.

The image above was generated by this code:

require("ray")
require("materials")

local s = nil
for x = -1, 1 do for y = -1, 1 do for z = -1, 1 do
local m
if x*y*z == 0 then m = gold else m = cyan end
local t = sphere3(m, 0.5):translate(v3(x,y,z)*1.5)
if s ~= nil then s = s + t else s = t end
end end end
s = s:transform(rotate3(0.3,1,2) * rotate3(0.3,0,2) * rotate3(0.3,0,1))

local l = Lights3:new(rgb(0.25,0.25,0.25))

render3(s, l, 788, 576, 4/3, 2)

One small tip when using tolua with recent versions of g++: activate the -Wno-write-strings flag to avoid drowning in a flood of:

warning: deprecated conversion from string constant to 'char*'

It is quite boring writing wrappers for ray42's C++ template classes because tolua doesn't seem to understand templates, maybe I should be using tolua++ or some other tool entirely.


text:
# INTERPRETING PCA ANALYSIS

I am having little trouble figuring our which variables are the most important when I am using PCA . What I am trying to do is see which variables explain the most variance when it comes to stock prices . What I have done is I took data from some stocks in the pharmaceutical sector (like JNJ,MRK ect.)and I took their P/S P/B ROE AND other variables and I would like to know which variables explain the most variance so I know what metrics to look at when I am analyzing the pharmaceutical sector . This was the result.

Importance of components:
PC1    PC2    PC3    PC4     PC5     PC6     PC7     PC8    PC9    PC10      PC11
Standard deviation     2.7288 1.7861 1.5533 1.1306 0.82578 0.71937 0.47079 0.34490 0.3150 0.18236 1.814e-16
Proportion of Variance 0.4654 0.1994 0.1508 0.0799 0.04262 0.03234 0.01385 0.00743 0.0062 0.00208 0.000e+00
Cumulative Proportion  0.4654 0.6648 0.8156 0.8955 0.93809 0.97043 0.98429 0.99172 0.9979 1.00000 1.000e+00

so I decided to keep 5 principle components because they explain over 90% of the data

My problem is how do I determine which variables are most important from these 5 principle components ? Could I use something like a weighted average of each variable making the weight based off of the proportion of variance and take the variables with the highest weights average ? Or is there a better way of determining which of my variables are the most relevant from a PCA analysis

these are the eigenvectors

Rotation (n x k) = (16 x 11):
PC1         PC2          PC3         PC4         PC5         PC6         PC7
Beta:M-3                     -0.29790642  0.06702808  0.043897343 -0.23444949  0.26922306 -0.52278907  0.49126902
Debt/Equity LF               -0.29683436 -0.20602790  0.209892052  0.17525538  0.17021916  0.22824284  0.13967642
P/S                          -0.13584463  0.37660138  0.371760998 -0.13147372  0.13251944  0.04785622 -0.07498348
P/B                          -0.32237181  0.04415421  0.294703959  0.01222229 -0.01493067  0.06389646  0.14404329
PM LF                         0.31231588  0.13244909  0.280519000 -0.04766506  0.01057485  0.13851709  0.10567161
OPM LF                        0.31383977  0.06628785  0.295610357 -0.05090070  0.03949326  0.20637913  0.07153909
R&D Exp T12M                  0.13290870 -0.22363789  0.356892802  0.17596955 -0.70388205 -0.08328041  0.23325195
ROA LF                        0.33128578  0.11822215  0.123556305 -0.15352214  0.15827191  0.04626632  0.41437205
ROE LF                        0.35240443  0.05558026  0.054402901 -0.00381858  0.09509125 -0.03775416  0.29445397
Rev - 1 Yr Gr:Q              -0.33213363  0.13173387  0.179946152 -0.04917693 -0.04327167  0.12309850  0.02891068
Dil EPS Frm Cont Op 1Y Gr LF -0.02935805  0.38139243  0.081834610  0.62033384  0.03574667 -0.03928716 -0.16499320
Curr Ratio LF                 0.02859583  0.48002784 -0.038108130 -0.37888227 -0.06938542  0.33198272 -0.18806338
P/E                           0.04731051  0.46627994 -0.033990479  0.41432037 -0.02392947 -0.30628066  0.12819470
Shrt Int Ratio:D-1           -0.33298583  0.01426119  0.008234069  0.10984204 -0.10586662  0.48387359  0.33537995
RSI: Period=14                0.06437034  0.09275629 -0.564351964  0.19383663  0.02711028  0.34214075  0.42631622
Tot Analyst Rec:D-1           0.15449771 -0.31749070  0.238832459  0.29221399  0.57364300  0.15502219 -0.09793154

hopefully you guys on stack exchange will share a little bit of your wisdom and help me out here . Thank you in advance .

IIRC, the signs of the PC are meaningless. +/-'ive doesn't itself tell you anything.

Rather, the cross-sectional, absolute max of the PCs will tell you which one is most important per item (eg: PC6 looks most important for Beta: M-3).

I think 6.6a and 6.6b in Cochrane's asset pricing touch on this (https://www.youtube.com/playlist?list=PLAXSVuGaw0KxVUym8IRkObSbUPEFaSbPt).

This blog post seems resonable: https://thequantmba.wordpress.com/2017/01/24/principal-component-analysis-of-equity-returns-in-python/

Generally, PC1, scaled to 100% weight, creates a long-short "Portfolio PC1".

These portfolios then tend to "look" like other observable assets.

Skimming this paper seems like it has some sample code, and was reviewed by someone: https://web.wpi.edu/Pubs/ETD/Available/etd-080614-144242/unrestricted/Chen,_Huanting_PCA_2014-07-31_FINAL_VERSION.pdf

The classic example is the level, slope and curvature exercise: https://faculty.chicagobooth.edu/john.cochrane/teaching/coursera_documents/bond_notes_2.pdf

You can likely recreate this with data on st louis fed's fred.

The larger question is "What are you trying to do?". PCA, IMO, is pretty confusing if you don't have a goal. PC1 is always the most important (in terms of variance explained) by default. That's just what PCA gives you.

• I am trying to see which variables wether it is price/sales ROE or Price/book explain the most variation in the data so I can know which metrics to look at when I am analyzing a sector – Pelumi Nov 5 '19 at 0:00
• Wouldn't a regression solve your problem? You may just be using a less ideal statistical model for your specific problem – jason m Nov 5 '19 at 4:23
• I know I know a regular multi linear regression model can help me out here I would just like like an improvement to the regular multi linear regression model . Would Lasso be a good idea here? – Pelumi Nov 5 '19 at 12:57
• I would definitely recommend a lasso regression in this case, it seems odd to use a PCA and then step back to find which individual variables describe variability. You may also want to check out stepwise variable selection techniques. – jdpy19 Nov 6 '19 at 17:36
• I acutally think random forest would be MUCH better than lasso. – jason m Nov 6 '19 at 20:35


text:
+0

# I need help ASAP

0
90
1

Find a function f(x) such that the line below is the graph of the equation $$|z-3i|=|f(z)|$$?

And

The square of the non-real complex number z  is equal to $$\overline{z}$$ . What is the real part of z?

Thanks so much!!!

Oct 11, 2019


text:
# Compile Regexes

In this task you have to write a program that reads a regular expression and generates another program that outputs whether an input string is accepted by that regular expression. The output must be a program written in the same language as your submission.

# Input

The input is a regular expression r matching the following ABNF (the initial production rule is REGEX):

REGEX       = *( STAR / GROUP / LITERAL / ALTERNATIVE )
STAR        = REGEX '*'
GROUP       = '(' REGEX ')'
LITERAL     = ALPHA / DIGIT
ALTERNATIVE = REGEX '|' REGEX

If the input does not match this grammar, the behavior of your program is undefined.

# Interpretation

Interprete the input as a regular expression, where * is the Kleene-star (meaning repeat left argument zero or more times), | is an alternative, ( and ) group and no operator at all concatenated. Grouping takes precedence over star, star takes precedence over concatenation, concatenation takes precedence over alternative.

A string is said to be accepted if the regex matches the whole string.

# Output

The program's output is another program written in the same language as your submission that reads a string s in an implementation defined way at runtime, outputs whether r accepts s and then terminates. Output may be done in a user-defined way although there must be only two distinct outputs for accepted and rejected programs.

You may assume that the input of your output program is never longer than 216-1 Bytes.

# Restrictions

Neither your submission nor any program generated by your submission may use builtin functionality or libraries that

• match regexes
• transform regular expressions
• compile regular expressions
• generate parsers from a grammar
• simplify the problem in a way that your submission becomes trivial

# Scoring

The score of your submission is the number of characters it. The submission with the lowest score wins.

# Testcases

All testcases contain a regular expression, a set of accepted strings, a set of rejected strings and an example program in C99 which is a valid output of a (hyptothetical) C99 submission.

## (empty regular expression)

### Accepted strings

1. (empty input)

1. foo
2. bar
3. baz
4. quux

### Example program

#include <stdio.h>

int main() {
char input[65536];
gets(input);

return input[0] != 0;
}

## (b|)(ab)*(a|) (a and b alternating)

### accepted strings

1. a
2. ba
3. abababababa
4. abab

### rejected strings

1. afba
2. foo
3. babba

### example program

#include <stdio.h>

int main() {
char input[65536];
int state = 0;

for (;;) switch (state) {
case 0: switch (getchar()) {
case 'a': state = 1; break;
case 'b': state = 2; break;
case EOF: return 0;
default:  return 1;
} break;
case 1: switch (getchar()) {
case 'b': state = 2; break;
case EOF: return 0;
default:  return 1;
} break;
case 2: switch (getchar()) {
case 'a': state = 1; break;
case EOF: return 0;
default:  return 1;
} break;
}

## (0|1(0|1)*)(|A(0|1)*1) (binary floating point numbers)

1. 10110100
2. 0
3. 1A00001

### rejected strings

1. 011
2. 10A
3. 1A00
4. 100A010
• I presume that having a program like return (regex.match(stdin) is not null) is not allowed. – beary605 Aug 18 '12 at 23:25
• You say that "The output must be a program written in the same language as the input", but the input is a regex. And the grammar you provide doesn't include the rule GROUP, which presumably defines literal brackets. – Peter Taylor Aug 19 '12 at 7:24
• @Peter Sorry, I meant to write they same language as the submission. – FUZxxl Aug 19 '12 at 10:04
• @beary605 Yeah, you're right. See the section Restrictions: Neither your submission nor any program generated by your submission may use builtin functionality or libraries that match regexes (...). – FUZxxl Aug 19 '12 at 10:13
• I think your second example program is incorrect, it's missing a loop around the outer switch – Hasturkun Aug 21 '12 at 11:09

### Ruby, 641651 543 characters

H=Hash.new{|h,k|[k]}
d=[[i=0,0,[]]]
o=[?(]
L="t,u,v=d.pop;q,r,s=d.pop;o.pop<?|&&(H[r]<<=t)||(H[q]<<=t;H[r]<<=u);d<<[q,u,s+v]"
gets.chop.chars.map{|c|c==?*&&(q,r,s=d.pop;H[r]|=[q,i+=1];d<<=[r,i,s];next)
eval(L)while/[|)]/=~c ?o[-1]>?(:o[-1]==?.
/[|(]/=~c&&d<<[i+=1,i,o<<c&&[]]||c!=?)&&d<<[i+=1,i+1,["s==#{o<<?.;i}&&c=='#{c}'&&#{i+=1}"]]||o[-1]=?.}
eval(L)while o.size>1
H.map{H.map{|k,v|v.map{|v|H[k]|=H[v]}}}
t,u,v=d[0]
$><<"s=#{H[t]};gets.chop.chars.map{|c|s=s.map{|s|#{v*'||'}}-[!0];#{H.map{|k,v|"s&[#{k}]!=[]&&s|=#{v}"}*?;}};p s&[#{u}]!=[]"  This ruby version became quite long because of several corner cases in the regex parser (maybe I should try a different approach). It expects the regular expression on STDIN and outputs the corresponding ruby code for the matcher to STDOUT. The program directly generates code for a NFA-ε which is then executed in the matcher. Test case 1: (output includes additional newlines and indentation) >>> s=[0]; gets.chop.chars.map{|c| s=s.map{|s|}-[!0]; }; p s&[0]!=[]  Test case 2: >>> (b|)(ab)*(a|) s=[0, 1, 2, 4, 9, 5, 10, 6, 11, 12, 14]; gets.chop.chars.map{|c| s=s.map{|s|s==2&&c=='b'&&3||s==6&&c=='a'&&7||s==8&&c=='b'&&9||s==12&&c=='a'&&13}-[!0]; s&[1]!=[]&&s|=[1, 2, 4, 9, 5, 10, 6, 11, 12, 14]; s&[3]!=[]&&s|=[3, 4, 9, 5, 10, 6, 11, 12, 14]; s&[0]!=[]&&s|=[0, 1, 2, 4, 9, 5, 10, 6, 11, 12, 14]; s&[5]!=[]&&s|=[5, 6]; s&[7]!=[]&&s|=[7, 8]; s&[9]!=[]&&s|=[9, 5, 10, 6, 11, 12, 14]; s&[4]!=[]&&s|=[4, 9, 5, 10, 6, 11, 12, 14]; s&[11]!=[]&&s|=[11, 12, 14]; s&[13]!=[]&&s|=[13, 14]; s&[10]!=[]&&s|=[10, 11, 12, 14] }; p s&[14]!=[]  Another example: >>> a|bc s=[0, 1, 3, 4]; gets.chop.chars.map{|c| s=s.map{|s|s==1&&c=='a'&&2||s==4&&c=='b'&&5||s==6&&c=='c'&&7}-[!0]; s&[0]!=[]&&s|=[0, 1, 3, 4]; s&[3]!=[]&&s|=[3, 4]; s&[5]!=[]&&s|=[5, 6]; s&[2]!=[]&&s|=[2, 7] }; p s&[7]!=[]  Edit: Added a transition to fix the bug PleaseStand noted in the comments. Also changed initialisation of state. • Input 011 for regex (0|1(0|1)*)(|A(0|1)*1) results in true - it should be false. – PleaseStand Aug 23 '12 at 2:23 • @PleaseStand Fixed. Please see my edit. – Howard Aug 25 '12 at 7:10 ## C, 627 characters This program treats its first command-line argument as the input and generates C code as its output. #define A(v) F[v]+strlen(F[v]) #define S sprintf char*B="&&f%d(s)||f%d(s)",*J="&&f%d(s+%d)",*r,F[256][65536];h=2;e(f,n,o,R,C,O,t,g){for(C=O=f;*r;++r)switch(*r){case 40:r++;e(g=h++,C=h++,0,0);r[1]^42?t=g:(t=C,S(A(t),B,g,C=h++),r++);o=!S(A(O),J,t,o);O=C;break;case 41:goto L;case'|':S(A(C),J,n,o);o=!S(A(O=f),"||1");break;default:r[1]^42?S(A(C),"&&s[%d]==%d",o++,*r,O^f||R++):(o=!S(A(O),J,t=h++,o),O=C=h++,g=h++,S(A(g),"&&*s==%d&&f%d(s+1)",*r++,t),S(A(t),B,g,C));}L:S(A(C),J,n,o);}main(int c,char**v){r=v[1];for(e(1,!S(*F,"&&!*s"),0,0);h--;)printf("f%d(char*s){return 1%s;}",h,F[h]);puts("main(int c,char**v){exit(f1(v[1]));}");}  Here is its output for (0|1(0|1)*)(|A(0|1)*1) (with newlines added): f11(char*s){return 1&&s[0]==49&&f7(s+1);} f10(char*s){return 1&&s[0]==48&&f9(s+1)||1&&s[0]==49&&f9(s+1);} f9(char*s){return 1&&f10(s)||f11(s);} f8(char*s){return 1&&f7(s+0)||1&&s[0]==65&&f9(s+1);} f7(char*s){return 1&&f0(s+0);} f6(char*s){return 1&&f2(s+0);} f5(char*s){return 1&&s[0]==48&&f4(s+1)||1&&s[0]==49&&f4(s+1);} f4(char*s){return 1&&f5(s)||f6(s);} f3(char*s){return 1&&s[0]==48&&f2(s+1)||1&&s[0]==49&&f4(s+1);} f2(char*s){return 1&&f8(s+0);} f1(char*s){return 1&&f3(s+0);} f0(char*s){return 1&&!*s;} main(int c,char**v){exit(f1(v[1]));}  If you provide valid input as its first command-line argument, it returns exit status 1. Otherwise, it returns exit status 0.$ ./regexcompiler '(0|1(0|1)*)(|A(0|1)*1)' > floatprog.c
$gcc -o floatprog floatprog.c floatprog.c: In function ‘main’: floatprog.c:1:519: warning: incompatible implicit declaration of built-in function ‘exit’ [enabled by default]$ ./floatprog '1A00001' && echo invalid || echo valid
valid
\$ ./floatprog '100A010' && echo invalid || echo valid
invalid

Either program, if you fail to provide the command-line argument, dereferences a null pointer, causing a segmentation fault. A sufficiently long regex will overflow the buffers of this submission, and the size of input to a generated program is limited by the size of the stack. However, all the test cases work.

Note that e(g=h++,C=h++,0,0); introduces undefined behavior. If, for example, generated programs do not compile, you can try replacing the statement with h+=2;e(g=h-1,C=h-2,0,0);, which is five characters longer.


text:
# Does a positive electron affinity actually correspond to the release of energy?

I read about the periodic properties — ionisation energy and electron affinity — in my book. It was quite intuitive that energy is required to remove an electron from the atom but I wonder why energy is released when an electron is added to an atom? Is it actually released or is it because of our convention that energy of electron at infinite distance from nucleus is 0, that we consider it to be released?

It may help to take a look at the two processes you are comparing in terms of reactions. Ionisation follows the following reaction:

$$\ce{A ->[][\Delta E_\mathrm{i}] A+ + e-}\tag{1}$$

This process involves tearing charges apart, separating a positive and a negative one. Even if the original atom was somewhat unstable, it will be unfavourable to remove that electron simply due to electrostatic interaction. You write in the question that you were able to deduce this already.

The electron affinity on the other hand describes the process in this following reaction:

$$\ce{A + e- ->[][EA] A-}\tag{2}$$

Here, a charged particle is approaching a neutral particle and we have the same number of charged particles (and the same charges) on both sides of the equation. This means that we don’t have a strong, obvious physical effect that will make all electron affinities sign-equal for very simple reasons. Instead, we need to consider the details more.

The process often involves a release of energy because most atomic configurations have space for extra electrons at little or no extra cost. Except for the noble gases and the second group, atoms don’t have completely populated sub-shells so there should always be a position available in a subshell at an acceptable exothermic energy level. While adding an electron will increase electron-electron repulsion and increase all energy levels by a certain amount, this increase is typically less than the first ionisation energy which corresponds to the energy level of the highest occupied atomic orbital. Thus in electron affinity, we in principle gain the entire ionisation enthalpy minus the destabilising contribution of the new electron. (Caution! This is a very simplified picture and not suitable for generalisation or even strictly for explanation. It gets the basic point across though.)

Therefore, most electron affinities are exothermic with the notable exceptions of group 2, group 18 and nitrogen.

Energy has to be released when electrons are added to atoms in most cases.

Otherwise, why would they ever form covalent bonds?

The whole point of a covalent bond is that electrons are stabilized by the attraction to multiple nuclei, which helps to hold the system together. Therefore, the system must be more stable when you add an electron to an atom.

Note that in the case of something like a neon atom, where adding an electron is not favorable is not the case, we don't form covalent bonds.

From the atomic perspective, even for a neutral atom, the nuclear charge is not completely shielded by all of the electrons. Some electrons are going to be on the other side of the nucleus from the new electron you're adding.

This is because potential energy is more in this case when electron is further from nucleus as the forces between them are attractive. As the distance is decreased between nucleus and electron, potential energy decreases. Since energy is always conserved, the net decrease in potential energy is released as any form of energy. However the energy is not released in all the cases. It depends on the net effect of the interactions of the electron with the nucleus and the electrons that are already present in the atom.