text:
Conference Paper

# IREX MPO: A multi-path option for the iREX inter-domain QoS policy architecture

Authors:
To read the full-text of this research, you can request a copy directly from the authors.

## Abstract

The inter-domain Resource Exchange (iREX) architecture uses economic market mechanisms to automate the deployment of end-to-end (E2E) inter-domain (ID) quality of service (QoS) policy among resource consumer and resource provider Internet Service Providers (ISPs). In iREX, each policy reservation is deployed on a single E2E ID path made up of the most "desirable" (i.e. cheapest and least congested) ISP resources. To accommodate ISPs that prefer redundancy when deploying ID QoS policy, in this paper we introduce an extension to the iREX architecture that gives an originating ISP a multi- path option (MPO) when deploying a reservation. MPO takes an initiating ISP's preference for redundancy and provides information about the available path options to achieve this preference in a distributed manner. Our simulation results show that while providing redundancy to the originating ISP using MPO does increase its resource costs in accordance to an ISP's preference, it only marginally increases overhead, and does not affect overall network performance - in fact the use of MPO lowers congestion.

## No full-text available

... Also, there are several proposals which loose the strict requirements (e.g. convergence and accuracy of route conditions) on protocol performance while they still expect some level of global coordination or information such as iRex and NIRA [7], [10] to be able to offer flexible and demanding services (e.g., QoS, Economic-incentive aware routing). For preserving generality of the routing solution, we cannot take an approach that purely depends on tier-based routing. ...
Conference Paper
Full-text available
It can be argued that, BGP, de-facto inter-domain routing protocol, provides fairly stable routes. Path stability is a desired product of that limited level of deterministic performance of BGP. To attain this performance level, BGP relies on keeping up-to-date (aggregated) global information by incurring the cost of control traffic and delayed convergence. In this work, we developed an Opportunistic Path-Vector (OPVR) protocol which provides nice trade-offs between path stability, routing scalability and path quality to enable flexible inter-domain level routing services. Our approach is to redefine routing problem as a set of smaller scale problems which can be solved locally without requiring a global coordination but local communication. We also provide guidelines on how to solve these localized routing problems efficiently. Our analysis show that our method provide a good compromise between scalability and opportunity through smartly randomized (non-deterministic) choices. Our experiments with OPVRs on Internet AS-level topology show us that OPVRs can provide non-deterministic, scalable path exploration mechanisms with reasonable control traffic cost.
... Initial work on iREX was previously published by Yahaya and Suda in [10], work defining the iREX architecture was previously published by Yahaya and Suda in [11], preliminary work exploring iREX efficiency was previously published by Yahaya, Harks and Suda in [12], and work suggesting a multi-path extension to iREX was previously published by Yahaya and Suda in [48]. ...
Article
The inter-domain resource exchange (iREX) architecture uses economic market mechanisms to automate the ad-hoc negotiation and deployment of end to end inter-domain quality of service policy among resource consumer and resource provider . In this paper, we explore iREX's network load distribution by comparing its performance to a lower bound for network congestion in two ways. We first present an analytical model of iREX in terms of an online algorithm and analyze its efficiency via competitive analysis. Our main result shows that the efficiency loss of iREX with respect to monetary cost is upper-bounded by a factor of 8 K/2 K+1, where K s the number of deployments, provided affine linear price functions are used. When the price functions are used to model congestion in the network, this result implies upper bounds on the efficiency loss of iREX with respect to network congestion. We then complement the analytical model with a numerical study using simulations.with optimal solutions derived from unsplittable and splittable multi-commodity flow optimization models. Our numerical results show that for nominal to high traffic loads of 40% or more, iREX deviates a maximum of about 20% from the lower bound, while the current method deviates a maximum of 300%.
Article
The Internet is a gigantic distributed system where the end-to-end (E2E) quality-of-service (QoS) plays an important role. Yet the current inter-domain routing protocol, namely, the Border Gateway Protocol (BGP), cannot provide E2E QoS guarantees. The main reason is that an autonomous system (AS) can only receive guarantees from its first-hop ASes via service level agreements (SLAs). But beyond the first-hop, QoS along the path from a source AS to a destination AS is not within the source AS's control regime. This makes it difficult to provide high quality-of-experience services to many Internet users even when many content providers are willing to pay for such high quality E2E guarantees. In this paper, we investigate the feasibility of providing high QoS-guaranteed E2E transit services by utilizing a (small) set of ASes/IXPs to serve as "brokers" to provide supervision, control and resource negotiation. Finding an optimal set of ASes as brokers can be formulated as a Maximum Coverage with B—dominating path Guarantee (MCBG) problem, and we show that it is in fact NP-hard. To address this problem, we design a $(\frac{1-e^{-1}}{2})$ approximation algorithm and also an efficient heuristic algorithm when additional constraints (e.g., the path length) are considered. We further analyze the APX-hardness of the MCBG problem to reveal the existence of the best approximation ratio. Based on the current Internet topology, we demonstrate that it is indeed feasible to provide high QoS guarantees for most E2E connections with only a small broker set: with only 0.19%, 1.9% or 6.8% ASes/IXPs serving as brokers, 53.13%, 85.41% or 99.29% of all global E2E connections can receive high QoSguaranteed services. Finally, we provide an economic model to study the behaviours of ASes when cooperating our brokerage scheme with the BGP protocol, and show that there are incentives to form and maintain such a brokerage coalition.
Article
Full-text available
This paper will describe roles and market actors enabling new forms of co-operation and competition using Ambient Networks technology and concepts. According to the Ambient Networks vision "any" user will be able to connect to "any" network, which will challenge traditional "one operator - one subscriber" solutions. Ambient Networks will stimulate an unbundled value network but will also facilitate the dynamic and flexible way of doing business in an environment with many access and service providers. The roles described in more detail in this paper are the Local Access Provider, Access Aggregator, Access Broker, Trusted Third Party, ClearingHouse, Compensation Service Provider and Service Aggregator.
Conference Paper
Full-text available
The Internet consists of thousands of independent domains with different, and sometimes competing, business interests. However, the current interdomain routing protocol (BGP) limits each router to using a single route for each destination prefix, which may not satisfy the diverse requirements of end users. Recent proposals for source routing offer an alternative where end hosts or edge routers select the end-to-end paths. However, source routing leaves transit domains with very little control and introduces difficult sc alability and security challenges. In this paper, we present a multi-path inter- domain routing protocol called MIRO that offers substantial flexi- bility, while giving transit domains control over the flow of traffic through their infrastructure and avoiding state explosion in dissem- inating reachability information. In MIRO, routers learn default routes through the existing BGP protocol, and arbitrary pairs of do- mains can negotiate the use of additional paths (bound to tunnels in the data plane) tailored to their special needs. MIRO retains the simplicity of BGP for most traffic, and remains backwards com pat- ible with BGP to allow for incremental deployability. Experiments with Internet topology and routing data illustrate that MIRO offers tremendous flexibility for path selection with reasonable o verhead.
Conference Paper
Full-text available
We consider two generic routing problems via multiple paths in a computer network wherein bandwidth can be reserved, and guaranteed, once reserved, on the links. The first problem requires that a message of finite length be transmitted from s to d within τ units of time. The second problem requires that a sequential message of τ units be transmitted at a rate of η such that maximum time difference between two units received out of order is no more than q. We propose a polynomial-time algorithm to the first problem, and present simulation results to illustrate its applicability. We show the second problem to be NP-complete, and propose a polynomial-time approximate solution
Conference Paper
Full-text available
In high-speed networks it is desirable to interleave routing and resource (such as bandwidth) reservation. The PNNI standard for private ATM networks is an example of an algorithm that does this using a sequential crank-back mechanism. We suggest the implementation of resource reservation along several routes in parallel. We present an analytical model that demonstrates that when there are several routes to the destination it pays to attempt reservation along more than a single route. Following this analytic observation, we present a family of algorithms that route and reserve resources along parallel subroutes. The algorithms of the family represent different trade-offs between the speed and the quality of the established route. The presented algorithms are simulated against several legacy algorithms, including the PNNI crank-back, and exhibit higher network utilization and faster connection set-up time
Article
Full-text available
The Border Gateway Protocol (BGP) is an inter-Autonomous System routing protocol. It is built on experience gained with EGP as defined in RFC 904 [1] and EGP usage in the NSFNET Backbone as described in RFC 1092 [2] and RFC 1093 [3]. The primary function of a BGP speaking system is to exchange network reachability information with other BGP systems. This network reachability information includes information on the list of Autonomous Systems (ASs) that reachability information traverses. This information is sufficient to construct a graph of AS connectivity from which routing loops may be pruned and some policy decisions at the AS level may be enforced.
Article
Full-text available
. This is a preliminary version of a paper prepared for the Tenth Michigan Public Utility Conference at Western Michigan University March 25--27, 1993. We describe the history, technology and cost structure of the Internet. We also describe a possible smart-market mechanism for pricing traffic on the Internet. Keywords. Networks, Internet, NREN. Address. Hal R. Varian, Jeffrey K. MacKie-Mason, Department of Economics, University of Michigan, Ann Arbor, MI 48109-1220. E-mail: jmm@umich.edu, halv@umich.edu. Some Economics of the Internet Jeffrey K. MacKie-Mason Hal R. Varian The High Performance Computing Act of 1991 established the National Research and Education Network (NREN). The NREN is sometimes thought of as the "successor" to the NSFNET, the so-called backbone of the Internet, and is hoped by some to serve as a model for a future National Public Network. It is widely expected that substantial public and private resources will be invested in the NREN and other high performance ...
Article
Full-text available
Classical routing and admission control strategies achieve provably good performance by relying
Article
Full-text available
. This paper was prepared for the conference "Public Access to the Internet," JFK School of Government, May 26--27 , 1993. We describe the technology and cost structure of the NSFNET backbone of the Internet, and discuss how one might price Internet access and use. We argue that usage-based pricing is likely to be necessary to control congestion on the Internet and propose a particular implementating of usage-based pricing using a "smart market". Keywords. Networks, Internet, NREN, NII. Address. Hal R. Varian, Jeffrey K. MacKie-Mason, Department of Economics, University of Michigan, Ann Arbor, MI 48109-1220. E-mail: jmm@umich.edu, halv@umich.edu. Pricing the Internet Jeffrey K. MacKie-Mason Hal R. Varian On December 23, 1992 the National Science Foundation (NSF) announced that it will cease funding the ANS T3 Internet backbone in the near future. This is a major step in the transition from a government-funded to a commercial Internet. This movement has been welcomed by private pr...
Conference Paper
This paper presents initial findings on how ambient networks technology will enable new ways to establish and manage access and service provisioning from a business perspective. The concepts of network composition and multi-radio multi-operator wireless access provide the framework for network advertising and discovery, which are essential first steps for allowing "any" user to be able to connect to "any" network. Technology support for different options of advertising are described followed by a discussion of the business related aspects including: i) payment schemes, ii) dynamic pricing, iii) use of identifiers for "frequent users", iv) use of public or "private" directories of offers and v) possibilities with alliances between providers. Finally, results of a case study on dynamic pricing are presented. The conclusion is that the proposed concepts of advertising and discovery indicate a very large potential for enabling a competitive market for both access and service provisioning including support for establishment of agreements on the fly
Conference Paper
Abstract, The inter-domain Resource Exchange (iREX) ar-chitecture uses economic market mechanisms to automate the deployment of end to end (E2E) inter-domain (ID) quality of service (QoS) policy among resource consumer and resource provider Internet Service Providers (ISPs). Previous simulation results have shown that iREX allows more coexisting ID policy deployments with less network congestion when compared to the existing method. In this paper we explore iREX's network load distribution efficiency limits by comparing iREX's performance to a lower bound for network congestion. We present an ana-lytical model of iREX in terms of a min-cost flow problem, and numerical results of efficiency loss between iREX simulations and derived optimal solutions based on multi-commodity flow optimization models. Our results show that for nominal to high traffic loads of 50% or more, iREX deviates a maximum of approximately 30% from the derived lower bound, while the current method deviates a maximum of 350%. Index Terms, inter-domain; QoS policy; resource allocation and management; network control by pricing; economics.
Conference Paper
This paper introduces the inter-domain Resource Exchange (iREX) architecture for the automated deployment of fault tolerant end to end (E2E) inter-domain (ID) quality of service (QoS) policy among resource user and resource provider Internet Service Providers (ISPs). iREX uses economics and fully distributed mechanisms to empower domains to self-manage the deployment of E2E ID QoS policy. In iREX, resource user domains select and reserve ID QoS resources to form E2E ID QoS policy while resource provider domains provide information about available ID QoS resources and support the deployment of policies. iREX promotes accountability by enabling the establishment of bilateral agreements between a resource user ISP and all resource provider ISPs, and promotes congestion- avoidance by enabling a distributed resource selection process that selects the least congested ID deployment path. With iREX, domains cooperate to deploy ID QoS policy while maintaining their autonomy at all times. Simulation results show that iREX blocks fewer reservations and causes less congestion than the existing method, and that iREX is able to recover from faults.
Conference Paper
Internet service provider faces a daunting challenge in provisioning network efficiently. We introduce a proactive multipath routing scheme that tries to route traffic according to its built-in properties. Based on mathematical analysis, our approach disperses incoming traffic flows onto multiple paths according to path qualities. Long-lived flows are detected and migrated to the shortest path if their QoS could be guaranteed there. Suggesting non-disjoint path set, four types of dispersion policies are analyzed, and flow classification policy which relates flow trigger with link state update period is investigated. Simulation experiments show that our approach outperforms traditional single path routing significantly.
Article
This paper presents the design of a new Internet routing architecture (NIRA). In today's Internet, users can pick their own ISPs, but once the packets have entered the network, the users have no control over the overall routes their packets take. NIRA aims at providing end users the ability to choose the sequence of Internet service providers a packet traverses. User choice fosters competition, which imposes an economic discipline on the market, and fosters innovation and the introduction of new services.This paper explores various technical problems that would have to be solved to give users the ability to choose: how a user discovers routes and whether the dynamic conditions of the routes satisfy his requirements, how to efficiently represent routes, and how to properly compensate providers if a user chooses to use them. In particular, NIRA utilizes a hierarchical provider-rooted addressing scheme so that a common type of domain-level route can be efficiently represented by a pair of addresses. In NIRA, each user keeps track of the topology information on domains that provide transit service for him. A source retrieves the topology information of the destination on demand and combines this information with his own to discover end-to-end routes. This route discovery process ensures that each user does not need to know the complete topology of the Internet.
Article
We study the relation between the number of firms and price-cost margins under price competition with uncertainty about competitors' costs. We report an experiment in which two, three, and four identical firms repeatedly interact in this environment. In line with the theoretical prediction, market prices decrease with the number of firms, but on average stay above marginal costs. Pricing is more aggressive than in equilibrium. Absolute and relative surplus increases with the number of firms. Total surplus is close to the equilibrium level, because enhanced consumer surplus through lower prices is counteracted by occasional displacements of the most cost-efficient firm. (JEL C90, C72, D43, D83, L13) Copyright 2005, Oxford University Press.
Conference Paper
The ambient networks project is developing advanced networking capabilities, such as dynamic multi-access, network mobility, together with availability of ensured service or network context. The Ambient framework offers a "plug-and-play" flexibility to accommodate different routing schemes for alternative scenarios, ranging from completely flat topologies hanging off a common core network to deeply nested topologies attached to a core. This paper considers example routing mechanisms to support and take advantage of these new networking capabilities, exploring the tradeoffs involved. In practice, the specific choice of routing algorithm will always depend on network evolution scenario, no one solution being universally "best".
Conference Paper
This paper reports on a study of traffic patterns among autonomous systems (ASes), based on traces taken at various points in the Internet. The traces display a highly nonuniform distribution of traffic on flows between pairs of hosts, networks, and ASes. Aggregation along coarser granularities, such as networks or ASes, accentuates this nonuniform distribution. In one typical trace, for example, the top 9% of flows between ASes accounts for 86.7% of the packets and 90.7% of the bytes transmitted. A highly nonuniform traffic pattern suggests that routers need to maintain only limited QoS flow state. The paper discusses the implications of this phenomenon on different proposed QoS mechanisms
Conference Paper
Quality-of-service (QoS) encompasses a wide range of non-functional characteristics, including reliability, security, and performance and is becoming increasingly important in business-critical distributed systems. Such systems are increasingly deployed in open networks, such as the Internet, where resource allocation and load varies highly. To meet QoS requirements in such an environment, systems need to be able to dynamically (re)configure and adapt to changing QoS conditions. This paper describes a model for a QoS negotiation mechanism. The model allows clients and servers in distributed object systems to negotiate for QoS agreements involving multiple QoS categories, such as performance, reliability, security, etc. The model includes both a protocol that enables agents to negotiate and a technique for calculating the worth of alternatives. The protocol handles negotiations involving multiple offers and counter offers. It evaluates an offer based on the absolute requirements for QoS levels and their relative worth to the negotiating systems. The protocol and the worth calculations are part of a QoS negotiation model that involves simultaneous negotiation over multiple QoS categories. We describe how negotiating applications communicate and evaluate offers. In addition, we describe the functions the negotiation mechanism requires from its environment. The protocol has been formally specified and simulated. We are currently investigating implementation approaches and prototypes for the full as well as simplified versions of the described model
Article
Classical routing and admission control strategies achieve provably good performance by relying on an assumption that the virtual circuits arrival pattern can be described by some a priori known probabilistic model. A new on-line routing framework, based on the notion of competitive analysis, was proposed. This framework is geared toward design of strategies that have provably good performance even in the case where there are no statistical assumptions on the arrival pattern and parameters of the virtual circuits. The on-line strategies motivated by this framework are quite different from the min-hop and reservation-based strategies. This paper surveys the on-line routing framework, the proposed routing and admission control strategies, and discusses some of the implementation issues
Article
Network delivery services providing "better-than-best-e#ort" service over the Internet are being studied, and are particularly necessary for multimedia applications. The selection and use of a specific delivery service involves negotiation between the user and the network; they agree upon specifications such as the type of service user packets will receive, the constraints the user tra#c must adhere to, and the price to be charged for the service. In this paper, we describe a protocol through which the user and the network (or two network domains) can negotiate network services. We refer to the protocol as a Resource Negotiation and Pricing protocol (RNAP). Through RNAP, the network service provider communicates availability of services and delivers price quotations and charging information to the user, and the user requests or re-negotiates services with desired specifications for one or more flows. RNAP protocol mechanisms are flexible enough to support multiple delivery service models, and allow dynamic re-negotiation of services during a session. Two di#erent network architectures are defined to support RNAP, a centralized architecture with a Network Resource Negotiator (NRN) administering each network domain, and a distributed architecture without any centralized controlling entity. Mechanisms are proposed for local price and charge computation, formulation of end-to-end prices and charges across multiple domains, and communication of this information through RNAP messages. Results of a prototype implementation are briefly described.
Article
As the Internet makes the transition from research testbed to commercial enterprise, the topic of pricing in computer networks has suddenly attracted great attention. Much of the discussion in the network design community and the popular press centers on the usage-based vs. flat pricing debate. The more academic literature has largely focused on devising optimal pricing policies; achieving optimal welfare requires charging marginal congestion costs for usage. In this paper we critique this optimality paradigm on three grounds: (1) marginal cost prices may not produce sufficient revenue to fully recover costs and so are perhaps of limited relevance, (2) congestion costs are inherently inaccessible to the network and so cannot reliably form the basis for pricing, and (3) there are other, more structural, goals besides optimality, and some of these goals are incompatible with the global uniformity required for optimal pricing schemes. For these reasons, we contend that the rese...
Article
Bandwidth brokers as proposed in the diffserv framework build on the process of setting up Service Level Agreements (SLA). This is a very static procedure, usually performed manually and based only on a simple description of the SLA. However, diffserv is suited to handle a more dynamic environment and to provide more than connectivity with its service classes. Our proposal enhances bandwidth brokers by including more significant information in SLAs such as the flow's destination network and pricing. In addition, we present a new per-hop behavior that supports flexible allocation of code points which is important to our approach. The system is targeted at large ISPs with good inter-connectivity. We implemented it on top of a flow-based simulation engine. The evaluation is based on parts of the current AS topology and characteristics of aggregated traffic. The results show an improvement of network utilization by up to 40% over a traditional, shortest-path routed inter-domain network for...
Article
vii 1 Introduction 1 1.1 Relation to Prior Work : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.2 Contribution and Organization of the Paper : : : : : : : : : : : : : : 3 2 Problem Formulation 4 3 Message Transmission Problem 5 3.1 Shortest-Widest Paths : : : : : : : : : : : : : : : : : : : : : : : : : : 5 3.2 Properties of Multipaths : : : : : : : : : : : : : : : : : : : : : : : : : 6 3.3 NP-Completeness of MTP : : : : : : : : : : : : : : : : : : : : : : : : 10 3.4 Approximate Routing Algorithm : : : : : : : : : : : : : : : : : : : : 14 3.5 Relation to Maximum Flow Algorithm : : : : : : : : : : : : : : : : : 16 3.6 Simulation Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 3.7 Delay-Bandwidth Product : : : : : : : : : : : : : : : : : : : : : : : : 24 4 Sequence Transmission Problem 25 4.1 Intractability Results : : : : : : : : : : : : : : : : : : : : : : : : : : : 25 4.2 Approximation Algorithm : : : : : : : : : : : : : : : : : : : : : : : : 28 5 Concl...
Article
We propose a QoS (Quality of Service) routing scheme in which a connection between a source-destination pair can be assigned to one of several alternative paths. The goal of our approach is to compensate for the inaccuracy of the link state information kept at network nodes. Starting from the well known algorithm by Dijkstra, we develop a collection of K-shortest path routing strategies and investigate their performance under a diverse set of network topologies and traffic conditions. We demonstrate that K-shortest path routing offers a lower blocking probability and more balanced link utilization than traditional schemes based on a single shortest path. Consequently, our approach makes it possible to reduce the frequency of link state exchange, and the incurred bandwidth overhead, without sacrificing the overall performance of the network.
Proactive multi-path routing, " in From QoS Provisioning to QoS Charging, ser
• J Shen
• J Shi
• J Crowcroft
J. Shen, J. Shi, and J. Crowcroft, " Proactive multi-path routing, " in From QoS Provisioning to QoS Charging, ser. Lecture Notes in Computer Science, G. Goos, J. Hartmanis, and J. van Leeuwen, Eds. Berlin Heidelberg: Springer, 2002, vol. 2511/2008, pp. 145–156.
Tariff distribution protocol (TDP)
• O Heckmann
• V Darlagiannis
• M Karsten
• R Steinmetz
• B Briscoe
O. Heckmann, V. Darlagiannis, M. Karsten, R. Steinmetz, and B. Briscoe, " Tariff distribution protocol (TDP), " Internet-Draft draft-heckmann-tdp-00.txt, March 2002.
This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the ICC


text:
×

Search anything:

# Similarity Search on Big Vector Data

#### Machine Learning (ML) data science

Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explored Similarity Search on Big Vector Data along with Nearest Neighbor Search (NNS) or Approximate Nearest Neighbor Search (ANNS).

1. Introduction
2. Definition
3. Datasets
4. Method
4.1. Directly Brute Force (for NNS)
4.2. LSH - Locality-Sensitive Hash (ANNS)
4.3. Graph-Based Algorithm (ANNS)
5. Summary

# 1. Introduction

Similarity search on vector data is a classical problem that have been researched for the past decades. In this problem, we have massive vector data as a "database", each vector represents a point in the hyperplane. A similarity search task is, given a new vector in or not in the database, we need to find the most (approximately) similar vector(s), and the similarity between two points is often calculate by L2 distance(Euclidean distance), inner-product or cosine distance. It's also known as Nearest Neighbor Search (NNS) or Approximate Nearest Neighbor Search (ANNS).

# 2. Definition

To be specific, vector data in such databases is produced by some neural networks, which means each vector is an embedding for a image/video/text. They may come from Bert, ImageNet, EfficientNet or any other DNNs.Nowadays, dataset's scale is explosively growing, we need to find a efficient way to solve the problem.

Let $N$ denotes the total number of vectors in such database, and
every element gets the same dimension $D$. Now we have a dataset $S = [s_{1}, s_{2}, s_{3}, ..., s_{N}]$ and every point $s_{i}$ represents a vector with dimension $D$, $s_{i} = [a_{0}, a_{1}, ..., a_{D-1}]$.
So the problem is, given a dataset S and a query vector $q$, find "Top-k" the most similar vector(s) T in S by calculate distance function.
$$T = arg min _{T \subset S} \Sigma _{x \in T} d(x, q)$$

Where $d$ is distance function and $d$ can be Euclidean Distance or Cosine Distance. We usually use the former i.e. L2 distance. When it comes to ANNS, the result T is not exact obtain from this equation.

L2 distance
$$d(x, c) = \sqrt {\Sigma_{i=0}^{D-1}(x_{i} - c_{i})}$$
where $x,c \in S$.

If we need exact result, it's NNS. If we need approximate result, it's ANNS.

# 3. Datasets

As mentioned above, datasets are embedding by neural networks. In this section, I'll list some famous datasets for NNS or ANNS here.

In last year, NeurIPS 2021 held a competition -

Billion-Scale Approximate Nearest Neighbor Search Challenge. In this game, some classical and new released datasets were listed. Such as BIGANN, SPACEV from Microsoft; DEEP, Text-to-Image from Yandex; SimSearchNet++ from Facebook, etc. Each dataset has 1 billion base point.

# 4. Method

We noticed that most of datasets get a big scale (1B) and the dimension of data is relatively high (96 - 256), even some "small" datasets, such as DEEP-1M, SIFT-1M and so on still own 1 million points. As a result of big scale dataset, search procedure needs to be accelerated by modern algorithm rather than brute force method. In front of these big vector data, we need a trade-off between accuracy and latency, so we propose ANNS. In ANNS, we allow the result points from search are not exactly the nearest point(s) of query, but ANNS provides the ability for online service because of low latency and tolerable error rate.

Following below methods are used for NNS or ANNS in past few years.

## 4.1 Directly Brute Force (for NNS)

This method was used to get exact answer from datasets. It requires a linear scan on the whole dataset, calculating function $d(q, x_{i})$ (mentioned in section 2) where $q$ is the coming query and $i$ in range(0, N-1). Then merge and re-ranking all result to obtain $K$ points which are exactly closest to query.

K-NNS

$$Result \ R = argmin_{R \subset S} \Sigma_{i=0, x_{i} \in R} ^{K} {d(x_{i}, q)}$$

## 4.2 LSH - Locality-Sensitive Hash (ANNS)

The main idea of using LSH to similarity search is simple. Assuming that two points $x$ and $y$ in high dimensional space are close, if there is a hash function $H$, then H(x) and H(y) may obtain the same result as long as they are close enough and function $H$ is appropriate.

## 4.3 Graph-Based Algorithm (ANNS)

Graph structure in search is more like a index. The well-designed index is used to perform suitable search algorithm.

This Figure[1] above explains how graph-based algorithm works in similarity search. Each point in original dataset represents a vertex in graph, and they will be connected by some edge in specific strategy then we obtain a graph index. In particular, the method to choose neighbors for vertices is based on distance calculation, by evaluating function $d(x, y)$, the algorithm select suitable neighbors for every vertex. Usually, people expect to build an approximate KNN graph which means every node in graph connects to its k nearest neighbors. The famous algorithms of building graph includes HNSW, NSG and so on.

Having a graph index, we can run a search algorithm on it.
As Figure 1(b) shows, search algorithm will find a path from seed vertex to approximate nearest results when a query(read star in figure) comes. Seed vertex is a starting point for search, which can be specify or just random. For finding the appropriate path, Firstly, put seed vertex in to candidates list, then evaluate the neighbors of current node in that list then put the new nearest nodes into it. By doing this, we are approaching to the approximate results. It's like a greedy search but having difference.

Pseudo code. (not really available to use, because it's very complicate to implement a similarity search system)
Details can be find in DiskANN source code.

//search procedure, Pseudo code

/*
k - number of result needed (topK)
l - number of current nodes in candidates_list
l_size - size of candidates_list
candidate_list - vector (sorted by distance to query)
queue - priority queue
*/

init_candidate_list(candidate_list) // init list with seed vertex & it's neighbor

int k = 0;

while(k < l) {
int current_k = l;
if(!visited(candidate_list[k])) {
visit(candidate_list[k]);
Node current_node = candidate_list[k];
Neighbor current_neighbor = get_neighbor(current_node);
for( node in current_neighbor) {
double d = distance(node, query);

if(d > distance(query, candidate_list[l - 1] && l == l_size) {
continue;
}
int location = insert_into_list(node); // insert node to candidates_list in suitable locatoin
if(location < current_k) {
current_k = location;
}
if(l < l_size) {
++l;
}
}
if(current_k <= k) {
k = current_k;
} else {
++k;
}
} else { // visited;
++k;
}
}
return candidates_list[0:k];

# 5. Summary

To sum up, I'm going to explain why this technique is important. Similarity search is deployed in many fields, include recommendation system, search engine, information retrieval, face recognition, etc.

Why?

Think about you are building a face recognition system for weak security, and there are 1 million people needed to be involved. You can't tolerant high latency when a recognition request comes. We are unable to deal with massive data if we only rely on "brute force" search. Similar to information retrieval, a retrieval system won't be deployed as service if the search latency is too high to tolerant.

This is a brief introduction for KNN or ANN search, different storage strategies, product quantization, and other method are not discussed here. We can learn more in big-ann-benchmark.

# References

[1]Wang, Mengzhao, et al. "A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search." arXiv preprint arXiv:2101.12631 (2021).

[2]Jayaram Subramanya, Suhas, et al. "Diskann: Fast accurate billion-point nearest neighbor search on a single node." Advances in Neural Information Processing Systems 32 (2019).

Similarity Search on Big Vector Data

format: plain


text:
mersenneforum.org New Wagstaff PRP exponents
 Register FAQ Search Today's Posts Mark Forums Read

2013-09-19, 23:57   #23
paulunderwood

Sep 2002
Database er0rr

32·7·53 Posts

Quote:
 Originally Posted by ATH I lost the other test on (2^13347311+1)/3 on the way, 10 days is a long time without any intermediate savefiles. Several other people seems to have these test running on faster computers than mine though, so I didn't restart it.
I've got 'em covered. One more day to go on a 4770k at 4GHz.

Last fiddled with by paulunderwood on 2013-09-20 at 00:08

 2013-09-20, 22:10 #24 paulunderwood     Sep 2002 Database er0rr 32×7×53 Posts Code: Running N+1 test using discriminant 2, base 1+sqrt(2) (2^13347311+1)/3 is Lucas PRP! (442900.4907s+0.0204s) and confirming ATH's result: Code: Running N+1 test using discriminant 2, base 1+sqrt(2) (2^13372531+1)/3 is Lucas PRP! (443577.1559s+0.0284s) The tests for (L+2)^(n+1)==5 (mod n, L^2+1) will take another 3 to 4 weeks Last fiddled with by paulunderwood on 2013-09-20 at 22:14
2013-10-17, 21:27   #25
paulunderwood

Sep 2002
Database er0rr

32·7·53 Posts

Quote:
 Originally Posted by paulunderwood The tests for (L+2)^(n+1)==5 (mod n, L^2+1) will take another 3 to 4 weeks
The tests passed for both PRPs.

I have emailed Henri Lifchitz requesting that the annotations for the PRPs in his database lists all our PRP tests.

Last fiddled with by paulunderwood on 2013-10-17 at 21:37

2013-10-18, 00:58   #26
ATH
Einyen

Dec 2003
Denmark

1011010011002 Posts

Quote:
 Originally Posted by paulunderwood The tests for (L+2)^(n+1)==5 (mod n, L^2+1) will take another 3 to 4 weeks
Sorry for my ignorance but n is the Wagstaff PRP right, but what is L ? and what is meant by "n, L^2 +1" in the modular expression? My guess is that (L+2)^(n+1)==5 for both (mod n) and (mod L^2+1) ?

(and yes I did spend a bit of time looking for an answer myself, before I get told to study myself :) But not too much since it is not that important)

Last fiddled with by ATH on 2013-10-18 at 01:02

 2013-10-18, 01:33 #27 paulunderwood     Sep 2002 Database er0rr 64138 Posts The modular reduction is done over "n" and "L^2+1". Here is a worked example for n=11 where L^2==-1 (mod 11, L^2+1) Code: (L+2)^2==L^2+4*L+4==4*L+3 (L+2)^3==(4*L+3)*(L+2)==4*L^2+11*L+6==0*L+6-4==2 (L+2)^6==2^2==4 (L+2)^12==4^2==16==5 This will work for all prime n==3 (mod 4), but is not proven that all composites will fail. Wagstaff are 3 (mod 4) To cover all n, I take minimal x>=0 such that jacobiSymbol(x^2-4,n)==-1, and check: Code: (L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1) This is the basis of my JavaScript program, which has the running time of 2 Miller-Rabin rounds. It is explained in my pre-print "Quadratic Composite Tests" where I used $\lambda$ instead of "L". The general "minimal x" method is good for n < 10^13 -- I am currently testing n < 7*10^13. Last fiddled with by paulunderwood on 2013-10-18 at 01:47

 Similar Threads Thread Thread Starter Forum Replies Last Post T.Rex Wagstaff PRP Search 190 2020-07-13 21:44 Batalov GMP-ECM 9 2012-08-24 10:26 davieddy Miscellaneous Math 209 2011-01-23 23:50 diep GMP-ECM 10 2010-07-26 21:33 T.Rex Math 0 2007-09-04 07:10

All times are UTC. The time now is 15:18.

Thu Aug 13 15:18:58 UTC 2020 up 11:54, 1 user, load averages: 1.81, 1.62, 1.47


text:
• Create Account

#ActualCC Ricers

Posted 20 September 2012 - 09:24 PM

Thanks, it solved the problem

If you want to have a look on my HLSL colored csm sampling functions that use it :
....

PS :
g_CSM_depths[split].x is the minimal depth of the #split map, g_CSM_depths[split+1].x is the maximal depth of the #split map.
g_CSM_depths[split].y is the depth bias of the #split map
Any suggestion or improvement is welcome

Instead of using if statements while looping through split indices get the correct split index by adding up conditional statements for all the split tests. This does away with the need for branching.

For instance, here is what I use for my single-pass CSM function:

cascadeDistances[NUM_CASCADES];

splitIndex = 0;
for (int i = 0; i < NUM_CASCADES; i++)

// Get shadow map position projected in light view

Here, linear Z depth is a value between the near and far world unit distances of the entire view frustum, not the splits. The cascadeDistances array is the list of far split planes in world units, listed from smallest to greatest. If linearZ > cascadeDistances[1], it also follows that linearZ > cascadeDistances[0] is true, therefore splitIndex is 2.

SplitIndex will always be less than the number of cascades, because cascadeDistances[n] is the farthest depth in the view, which linearZ will always be less than.

#1CC Ricers

Posted 20 September 2012 - 09:23 PM

Thanks, it solved the problem

If you want to have a look on my HLSL colored csm sampling functions that use it :
....

PS :
g_CSM_depths[split].x is the minimal depth of the #split map, g_CSM_depths[split+1].x is the maximal depth of the #split map.
g_CSM_depths[split].y is the depth bias of the #split map
Any suggestion or improvement is welcome

Instead of using if statements while looping through split indices get the correct split index by adding up conditional statements for all the split tests.

For instance, here is what I use for my single-pass CSM function:

cascadeDistances[NUM_CASCADES];

splitIndex = 0;
for (int i = 0; i < NUM_CASCADES; i++)


text:
# grit 0.8.4 (out with the old bugs, in with the new)

Okay, so it's been a while, but there's finally a new version for grit.

First of all, the vector::insert should finally be fixed. And there was much rejoicing. I've also added an option for forcing the map palette-index (-mp <num>, which should help with NDS backgrounds that use ext-palettes.

Also – and this one is pretty big – I've completely replaced the tile-mapping routines for something more general. The new method should be able to handle variable-sized tiles (-tw <n> and -th <n>) and is mostly independent of bitdepth. Specifically, bitdepths over 8 bpp can be handled as well, at least in principle. It also means that the external tileset can be a metatile-set as well now, which is good if you're using metatiles.

With this new method also comes a way to create a custom bitformat for maps (-mB flag). I'm not entirely sure how this can be used yet, but using more than 10 bits for the tile-index, or a 1bpp collision map should be possible now.

Since this is a fairly major change, I kinda expect there's still some bugs in the system. I have tested it for a number of options, but you know how it is with multi-platform stuff. In particular, if any of you big-endian-system users have trouble now, this will probably be the cause.

And now I will leave you with a …


text:
12:01 AM
4

If a caster has spent the duration of the Levitate spell moving upward to 2000' how long would it take to float back down again?

12:17 AM
is anyone here super good at google sheets?

How super do you need?

Dunno, enough to tell me if something can be done, so I try and crack it, or avoid losing time to it xd

You can do anything if you believe in yourself

What is it you need done? (We wont know if we know until we know)

I'm trying to make a button that selects a few cells in 2 columns, and marks them somehow (like changing color or writing something in them, so they can't be selected in the next randomization)

12:20 AM
3

The demiplane spell creates a door that leads to another plane of existence: You create a shadowy door on a flat solid surface that you can see within range. The door is large enough to allow Medium creatures to pass through unhindered. When opened, the door leads to a demiplane that appears ...

Also I would have a couple of tables with player roles, and I'd like to just write the names somewhere and randomly assign them
I've seen magic done with google sheets, like character sheets for rpg games that autocalculate everything, so I'm guessing this isn't especially hard to achieve, but I dunno

What's with the multiple randomizations?

It's to play secret hitler... The players are assigned randomly usually, and then every turn they have to draw from a deck of cards so I wanna fake that via randomizing wich cards are selected and taking them out...
All of that can be done manually, but I kinda wanna try and make a google sheet that makes it automagically, so the role of director is not cumbersome and my friends might be liable to want and take the mantle

Set up a range, randomise it and have specific players be specific cells in the range?

for example, yeah

12:28 AM
Yep. To simulate a deck of cards, rather than select a random card each time, it's easier to pre-randomize it and then increment the index of "top" card every time you draw.

hmm
makes sense

So you start with a column of X elements, and then shuffle it. Now your deck is randomized. Then "draw" the first N elements (which can be a column of N player names), and set the counter to N+1.

12:45 AM
@skullpatrol No worries--the "I work for a living!" line is just an old saw.

I wish I could do an if, or a case, in google sheets T_T

The syntax is something like =IF(<condition>,<formula if true>,<formula if false>)

@Helwar I think virtual table top has a secret hitler module. At least that's how I played it last time.

@MikeQ /facepalm, thansk a lot
@GcL what do you mean by virtual table top? (I have Tabletop Simulator but that's for playing live :S)

yeah... Tabletop Simulator. That's the one.

12:58 AM
@GcL May god pay you with not many children but as many tries as possible

You're trying to do a random selection without replacement for the chancellor and prime minister?

@GcL what do you mean?

Given 99 randomized bottles of beer on the wall, you take one down and now 98 remain, and you can't take the same bottle twice. Random selection without replacement.

You've got a list of players and you want to choose one for PM and one for Chancellor, but it can't be the same two as the previous round?

hummm no, that is selected by the players themselves, isn't it?
I just want to assign the roles (fascist, liberal, hitler)
like... you open the google sheet, have a dropdown to select how many players, write their names, click a button, and "liberal" / "fascist" / "hitler" appears in the cell to the right of the player names

1:04 AM
Gotcha. That should be easier
Buttons, not so much

i'm on it, I'm quite thick... but I'll get it eventually

I know that button logic exists, and column shuffling exists, so I imagine it's possible to trigger a shuffle via a button

you can't have on demand functions? :S

Easily? Not with formula. You can intentionally make a condition that doesn't call anything else until the correct number of inputs are present.
E.g. You could have a field to enter the number of players, and then a conditional to require the length of the player names column match before calling the randomization logic.

that might work

4 hours later…
5:06 AM
6

I want to make a character that uses two daggers, but I know that a character using daggers would not be as good as a character using shortswords or almost any other weapon. By "good", I mean approximately the same damage output as other characters. He uses daggers because I thought a character t...

5:47 AM
@HotRPGQuestions I thought [mundane] weapons never interacted with your alignment in DnD
on the other hand, maybe you're less good if you kill less goblins than the others?

1 hour later…
7:17 AM
I think you are more good if you kill fewer goblins
:P
Killing more things isn't a great benchmark for morality
XD

@trogdor I mean DnD "GOOD" basically stands for "Genocide Of Ogrish Demihumans"
Hmm, that's actually something that gets me thinking. Dungeon World has a move for carousing: spending the lööts you've acquired for a great feast and revelry, and getting new contacts and possibly trouble for it. Where's the equivalent move for good works? Characters who'd sooner build schools and clinics for the less-affluent species of the world might find it useful
I've always fancied playing characters who invest their gains to society somehow, and that might be something that should, in an AW engine style, have a bit of mechanical attention to work the best.

@kviiri I'm sorry, Mario. Your ethical downtime is in another game.

@BESW If Mario uses the warp zones a lot, I wonder if all the Toad warriors stay imprisoned forever

(Dungeon World is designed as a simulator of D&D-like stories in ways that may be more humane for the table, but part of simulating D&D-like stories is upholding rather than challenging the injustice of the status quo.)

7:33 AM
@BESW Aye. I brought it up because of the disconnect: in our games, both spending money to carouse and donating to charity are popular "black holes" to pour money in for no purpose apart from shallow RPG (shallow because it never has any impact beyond the immediate scene). So it's particularly jarring how it mechanizes one but not the other

One of Bell Songs' "downtime" moves is:
> Build. Build something that will last in your Home. Alternately, repair something that has been damaged in your Home.

@RandomDudeWithAKnife Isn't that already a homebrew by Matt Mercer? dmsguild.com/product/239392/…

@BESW Aye, that's exactly something I'd like :3

@kviiri btw, I have not yet read most of the rules (or most of the Commander class description), but to your knowledge, how does the Commander play, and how hard is it to get a grasp of as someone who hasn't played 13th Age (and has played 5e :P)? @KorvinStarmast feel free to weigh in too if you've read the Commander class description.

@kviiri Interestingly, most moves involve some mechanical benefit like marking Bond or restoring Rascality, but Build? it just improves your Home and that's considered benefit enough.

7:41 AM
@V2Blast The Commander seems loosely based on 4e Warlord. The basic core mechanic of the class seems to be that you have Command Points, which you can use to grant your allies buffs on their turns. You gain more Command Points by participating in the fighting or by spending your action to muster them (which gives more points but you don't get to attack)
I didn't read the class too carefully yet, but the design intent seems to be that you can pepper a few points around every combat but don't "dominate" your allies too much
@BESW Yeah. There's a bit of difficulty in portraying works of charity well in a mechanical sense, because it kinda devalues the idea if its main purpose becomes too transactional.

@kviiri I guessed it was inspired by/based on the warlord, but I've never played 4e so I didn't know exactly what that implied in practice
Thanks :)

@V2Blast Just a sec, I'll look up a few example abilities
For note, I own only the Core book of 13th Age and the 13 True Ways supplement, so if you find other sources pls don't regard them as canonical x) I don't intend to enlarge my collection and don't want to study more
@V2Blast Examples of Commander interrupt actions:
- 1 point: Allow an ally to pop free from an enemy as a Quick action (normally it's a Move action iirc?)
- 1 point: Allow an ally to Rally (self-heal with a Recovery) as a Free action
- 2 points: Allow an ally to re-roll an attack (and use the new result)
(these are leveled so not all are available initially, but they can be buffed by feats)
In addition, Warlords have Tactics. They're essentially powers that buff an ally or the whole party either immediately or over time
You get a particular number of commands and tactics based on your level, and get to divide them between Commands and Tactics as you choose.
Similar to how Bards get to choose between Spells and Songs

8:14 AM
@kviiri Thanks! :)
I'll have to read it a bit more at some point but it sounds like something I'd be interested in trying out (mostly because it's not a thing in D&D 5e right now)

You gain 1d3 command points when you hit with a melee attack, it can be improved by feats. The alternative to leading from the front is "Weigh the situation" which uses the standard action but gives 1d4 points instead. Both have their own feats that improve upon them further

interesting

Notably the first one, in addition to providing less points, only works on a hit. Warlords deal damage on miss too, like many 13th Age classes, but if an ability like that triggers on a hit it must actually hit

8:30 AM
@kviiri I can't argue against that
honestly XD

5

Etherealness lasts for 8 hours and doesn't require concentration: You step into the border regions of the Ethereal Plane, in the area where it overlaps with your current plane. You remain in the Border Ethereal for the Duration or until you use your action to dismiss the spell... A Short Re...

9:30 AM
@V2Blast If I was not the GM I'd make a monk, I love those forms they've got. Or Sorcerer, with their breath weapons and chain spells. Seems both fun and unpredictable, but in an enjoyable way
Or cleric because I like inventing pantheons

3 hours later…
12:28 PM
@nitsua60 Aah, given that I've got two cousins and an aunt (and a sister in law) who were educators, I'm not buying that for a minute. :)
@V2Blast OK, I'll need to take a look at that later. Wife is going a bit frustrated with filing stuff on line and getting time outs, so it may be a day or so before I can try to "grok" the Commander kit/build.

@KorvinStarmast you know filing is extended, right?

@NautArch what I know and what she is obsessed with completing are two different things. :)

@KorvinStarmast I have no idea what you're talking about :P

@NautArch Plausible deniability is the best kind.

1:29 PM
And my Roll20 group just went from 3 to 5 to 7 people.
I think I may need to increase the monsters

@KorvinStarmast Ugh... that's even true for my own self. "You know that's totally unnecessary to worry about?" I say to myself. "You shut your face hole and let me worry about what to worry about," I respond to myself.

@GcL As long and your internal monologue doesn't erupt outwards in public you have nothing to worry about. :)

@KorvinStarmast My cat's either don't understand English or really don't care about what I have to say. Probably both now that I think about it.
@MikeQ I would recommend Magical Kitties Save the Day!, but it doesn't look like there's a way to get in on the early release pdfs anymore and the game doesn't ship until august. However, it is a highly entertaining system for "yes, and..." style of collaborative story telling broken up into scenes.

1 hour later…
3:10 PM
3

Blood in the Water (Tome of Battle, p. 86) states: While you are in this stance, you whip yourself into a terrible rage. When you score a critical hit against an opponent, you enter a near frenzied state from the sight and smell of blood. You gain a +1 bonus on attack rolls and damage rolls. ...

3:46 PM
@KorvinStarmast Thanks. You're making me blush. (Though I will say: if your cousins and aunt are anything like most teachers I've met, they probably work harder than me!)

@nitsua60 Grading papers and homework and exams... so many extra hours on top of the job one gets paid for.

4:37 PM
@GcL It's true that a lamentable fraction of people confuse face time for "work time" in this career. Then again, I have two summer months off for no good reason, so I try to keep my head down.

@nitsua60 Work smarter, not harder. ;) I figure that's where you save time. :)

@nitsua60 My experience was only with mathematics and computer science. My recollection was that the hours for the time off didn't balance the time grading papers and other overhead. This was especially so if you count the time as overtime.

Okay, so as I said, my group went from 3, to 5, and now to 7. They are finishing up an encounter but moving somewhat shortly onto a new one that was just supposed to be Medium. (3 level 8s vs a CR 7 monster)
I may make it Hard with 3 CR 7 monsters
does that sound right?

How many players and what's their character's levels?

@GcL level 8. Now a total of 7.

4:44 PM
Seven level 8 characters? Damn.

But I think White Plume mountain may have been for 3-4 PCs.
But it doesn't actually say anywhere that I can find.

I think that encounter would be easy. You get a lot of extra actions with more players.
Do the encounter tables scale to seven players?

@GcL STill easy to move it from a single CR7 to 3 of them?

Sorry... had that backwards. The table says that should be hard, but in practice having that many actions available to a coordinated group should trounce the encounter pretty quickly.
Just the probability of crits with so many attacks makes it difficult to win against superior numbers.

@GcL Yeah, i'll also be playing the intelligent monsters very intelligently.

4:50 PM
I used to calculate how many kobolds it would take to take down my player's characters.

But I'm going to have to increase the numbers.

@NautArch Does that include the possibility of avoiding the fight altogether and then stalking the party to hose them later?

I'll see how tonight goes. I'll also probably increase the chances of random encounters and increase the encounter difficulties.
@GcL That's not really how White Plume is set up.

I found it useful to give the higher CR creatures minions instead of adding another monolithic target. They get better bang for their AOE buck and found it satisfying to lay waste to a swath of enemies. Or terrify the minions away with some non-combat tricks.
@NautArch Larger groups should attract more attention from more powerful predators while scaring away the small stuff.

@GcL yea, but then I'm basically rewriting the module. I was hoping to make it easier on me :P
Like there's a room with a bunch of Flesh Golems in it. I can add more of them (which narratively fits) or I have to come up with something else. It's also not a big room.

4:55 PM
Small spaces are problematic for big groups. Especially with the 5' square thing. I usually narrate cramped fighting in a theater of the mind style with very little maneuvering available. However, that's probably not the way to go for a big group in regular sized spaces.
I think you probably have too many players for canned material. Most max out a 5 players.

@GcL I think you're right. I'll see how tonight goes and then figure out what to do.

I'll be interested to hear how it goes and what you come up with.

I'll be back on tomorrow :P
I think it'll be doable. I need to look at the encounters, but most have the space. And I'll see what they do and try to reward cleverness.

5:12 PM
So I'm looking at the rules for multiclass spellcasters because there was a QA about it that I thought missed some information. I swear there used to be a rule that said how to factor spell slots if you're multiclassing and have something like Eldritch Knight (ie. base class doesn't have spell slots but subclass grants a few later) you add 1/3 of your level in those classes to the total but I can't find it now.
All I can find it this
> Spell Slots. You determine your available spell slots by adding together all your levels in the bard, cleric, druid, sorcerer, and wizard classes, and half your levels (rounded down) in the paladin and ranger classes. Use this total to determine your spell slots by consulting the Multiclass Spellcaster table.

@Himitsu_no_Yami PHB version, not the Basic rules version, because the relevant subclasses aren't in the Basic Rules

Ahhh thank you
Glad to know I'm not going crazy
That question you marked as a dupe tho. The actual question isn't answered in the question it's a dupe of. (it doesn't go into the 1/3 spellcasters but OP specifically called out one of the 1/3 casters)

@Himitsu_no_Yami then we should bounty the original to get it fully answered
But not having it fully answered doesn't mean the question isn't the same.

@Himitsu_no_Yami There's nothing special about the 1/3 casters in this case is there?

And, to be honest, I didn't look at the answers before dupe-hammering.I just looked at the questions and they seemed identical.

5:19 PM
actually, looking at it more closely, it was asking about spells known so I think we're good
This is why I need sleep -.-
I just realized, do we not have a question about multiclass spell slots at all? I was looking for one to make sure it was good (since I spent all this time staring at the rules) and I'm either blind or there isn't one or I'm really bad at searching (probably the last one tbh)

The half and third casters don't do anything with multi-classing when it comes to prepared/known spells IIRC. Though they do impact spell slots and I wish we also had a big question explaining multiclassing spell slots

@Medix2 Yeah, I noticed the first half of that. I misread the original question

I asked about the various multiclassing questions we have here, but yeah, nothing really happened
Though, looking back, I certainly could've asked the question better or perhaps split it out into a few questions

If I can figure out how to word it nicely I'll make and self-answer a good multiclass spell slots question

Just make sure to include Warlocks and Wizard+Eldritch-Knight
I was debating doing that as well

5:31 PM
Yeah, I know ALL about warlocks lol they're my most played class

I did just close this question and this question though I'm unsure if that was the correct move

looking at the questions I would say that you were right to close them

Though @Himitsu_no_Yami We do have this question

it explains how spellcasting and pact magic combine but not much more. I'm working on a question right now to explain everything

Yeah, just pointing that one out, thanks so much

5:47 PM
No problem. Interesting side note, I just made a level 20 example character to show the different multiclass spell slot calculations and it only totaled up to a level 8 spellcaster lol

I've now closed some more questions and cleaned up my original question so you can look there for what things have already been asked about spell slots. (Well, the ones I found at least)

I can't actually access Meta at work. It's blocked (even though chat and main site aren't)
QA posted, let me know if you see any way to improve it

6:08 PM
I think including the actual table would be helpful, you could also talk about how the spell slots can be used and not just which ones exist. But that would require a change to the question itself...

I'm not sure how to include the table and I did mention that the slots could be interchangeably used
unless you meant something else

Yes but the actual question only asks how to determine how many spell slots you have, not how you can use them
Some already existing questions of note: here, here, and here

5

If I am trying to intimidate someone by casting earthquake centered on myself, do I also need to make the dex save to not fall prone? Or, am I not at risk?

6:41 PM
@Himitsu_no_Yami I can edit in the table if you'd like

Go for it
Also someone voted to close my question as a dupe lol
Erm I don't think that quite worked lol

Oh? Did you refresh the page?

ah, refreshing fixed it

The table can also be found here for free though it's from the Basic Rules so it doesn't mention Arcane Trickster or Eldritch Knight

Before refreshing I saw a bunch of \begin{array}{|c||c|c|c|c|c|c|c|c|c|} \text etc

6:51 PM
Yeahhhh that happens, it's kinda funny to see

thought I found my way to r/softwaregore for a minute
I'll also try to address the issues in your comment once I'm more awake. I'm half asleep at work rn

7:05 PM
@Someone_Evil good catch with the Artificer there! I forgot about it and it wasn't discussed in PHB
(probs for the same reason EK and AT aren't discussed in Basic rules)

It's also newer than either of those documents

so yeah, the same reason basically
EK and AT aren't detailed in basic because the subclasses aren't in basic

Thanks (I think) for altering the table as well

Artificer isn't in PHB so yeah
Also, with this question posted, my time spent staring at the rules wasn't wasted lol

@Medix2 That would be part scientific training and part gridded tables making me go cross-eyed

8:07 PM
I don't understand why people thought my question was a dupe. Spell slots and spells known are clearly different if you take the time to actually read what the question is lol

Yeah same... The nearest thing to a duplicate is probably "Multiclass Spellcaster: Do the involved classes share the same pool of spell slots? which doesn't actually ask about how you can use the spell slots nor how to determine which ones you actually have. Though I don't know that your question, as stated now, asks those things either (which one's you can use and how you can use them - shared pooling)
Though the shared pool question could just be left open (and removed from your answer) to answer that part of the question since, well, it already answers exactly that part

8:33 PM

Apparently the linebreak messed with character limits or something
Important questions to me: How many spell slots do I have (also edge cases like this, this, and this)? Which class uses them / Is it a shared pool (already answered) and related questions on spell slot recovery and Spellcasting + Pact Magic

oh, yeah, linebreaks make all text fixed font or something I think

It's a lot of inter-related stuff but at least 8 of the questions in my Meta question are answered by yours so maybe the edge cases and links above should just be left open and don't need to be addressed in your answer/question
I wasn't really sure how to proceed which is why I asked the Meta question...

8:54 PM
I'm gonna have to change the numbers around a bit actually. I had a level 2 Arcane Trickster listed which isn't possible

9:25 PM
@NautArch oof. why. how.

@Medix2 I just updated with a lot more info. Tell me if it needs anything else (and if needed, how I can reword the question to make everything fit together)

@Himitsu_no_Yami I believe you're calculation for EK + AT is incorrect. It should be 3 + 5/3 + 4/3 + 4/2 = 3 + 1 + 1 + 2 = 7 (EK and AT are divided separately) as gone over here

The accepted answer on that question says (ranger + paladin)/2, rounded down

Then perhaps explain that it's ambiguous in that case... or ignore it

I think it feels more correct to add them together

9:37 PM
I mean, the opposite answer has more upvotes, I'll be honest, I hadn't noticed there were competing answers, so maybe it should be left out...

Was there anything else you noticed though?

Don't think so

awesome

Maybe using the quote "Once you have the Spellcasting feature from more than one class, use the rules below. If you multiclass but have the Spellcasting feature from only one class, you follow the rules as described in that class." could help somewhere, but I'm unsure

@Himitsu_no_Yami That seems like a sound IT policy.

9:43 PM
@GcL ikr
You should see how bad the filter lists can be here
teeechnically.... we're not supposed to access anything that isn't work related but for the most part, nobody cares

@Himitsu_no_Yami More correct for min/maxers! I like the spellcasting is a tough discipline so you round those levels down before you add them. Also makes going full spellcasting class more valuable.

Oddly enough, if they added another upward rounding class then doing them separately becomes a better option since 3/2 + 3/2 would equal 4

I'm not a min/maxer, I'm just a maxer
:P
*glances over at his Skyrim save* probably too much so

@Himitsu_no_Yami All swords are double edged. If not, it's a messer.

I just try to max everything

9:51 PM
I now see why they wouldn't make another upward rounding caster though...

@Medix2 I mean at this rate we won't get another class until 2026, so I wouldn't worry about it

@V2Blast three more from my primary table (just one outlier now) and a guys brother in law

@Someone_Evil Hopefully not.

@GcL Hoping for more classes before that, or none at all?

@Someone_Evil No more, please. The existing ones and their variants are more than enough to keep the option space open enough. I don't want another 3.5e

10:02 PM
I want more Warlock subclasses

To what end?

just more options for Warlocks. I like seeing the different ones

I'm not sure, I don't have anything specific

What different thing do you not feel like you have already?

10:12 PM
I really don't know, I like seeing what they come up with tho

Warlock subclasses are... Complicated

Just more patron options would be good?

Since you have to account for Invocations if you want those too

More patron options would be really cool
I'm also very interested in more pact types (tome, chain, blade)

@Medix2 The whole warlock class is... complicated from a design pow

10:15 PM
Spell, Utility, Melee... what thing would you want a pact about?

Control/Zoning?

I couldn't say, I just feel like the three we have are rather limited

Limited along what mechanic?

@GcL Defence?

Not so much in mechanics but in options.

10:17 PM
Options for what aspect of the game?

I can't explain it but I feel like there should be more than those 3 options for pact boons

So more pacts. What else do would you like to see a pact offer?

Different utility is also where you can find more options

Like I said, I don't have anything in mind myself

Would three more pacts that essentially offer the same mechanics but with a different skin or flavor be good?
or what about the options doesn't seem like enough if it's just not the number of options?
@Someone_Evil What other utility do you think you'd like to see?

10:24 PM
I'm really not sure. I'd need to see specific ideas

@Himitsu_no_Yami Pact of the pamphlet. Exactly the same as pact of the tome, but shorter format and easier to hand out door to door.

@GcL lol funny but no I think it needs to be different than what's already there. I never was a fan of reskins

There was a Pact of the Talisman in a recent UA

@Himitsu_no_Yami Pact of the Library. Minus 5' movement for +1 spell slots.

@GcL That's pretty cool actually. I'm always short on spell slots cus I burn them too early lol

10:35 PM
@Himitsu_no_Yami Smoke em' if you got em.

For D&D DMs or anyone looking to buy any of Mike Schley's maps (he's one of the main map artists for many official 5e adventures), he's currently got a 50% off coupon code (2020Vision) for digital products that can be used as many times as you like, valid until April 30th: twitter.com/schley/status/1245027624503607296
4

3

I was looking at the piercer and noticed that it's attack not only has a Hit outcome, but a Miss line as well that is both fun and fits the attack. My sources are all hardback (not D&D Beyond), so I don't have an easy way to search through them, but as far as I can tell, the piercer is the only c...

1 hour later…
11:57 PM
@V2Blast that's great news. Nice find. Thanks! :)


text:
# What Is 24/100 as a Decimal + Solution With Free Steps

The fraction 24/100 as a decimal is equal to 0.24.

In arithmetic, a fraction is a number stated as a quotient in which a numerator is divided by a denominator. Both are integers in a simple fraction. A complicated fraction contains a fraction in either the numerator or the denominator. A suitable fraction has a numerator that is less than the denominator.

Here, we are interested more in the types of division that results in a Decimal value, as this can be expressed as a Fraction. We see fractions as a way of showing two numbers having the operation of Division between them that result in a value that lies between two Integers.

Now, we introduce the method used to solve said fraction to decimal conversion, called Long Division which we will discuss in detail moving forward. So, let’s go through the Solution of fraction 24/100. The Lond Division method can be seen in the figure 1 below:

Figure 1

## Solution

First, we convert the fraction components i.e., the numerator and the denominator, and transform them into the division constituents i.e., the Dividend and the Divisor respectively.

This can be seen done as follows:

Dividend = 24

Divisor = 100

Now, we introduce the most important quantity in our process of division, this is the Quotient. The value represents the Solution to our division, and can be expressed as having the following relationship with the Division constituents:

Quotient = Dividend $\div$ Divisor = 24 $\div$ 100

This is when we go through the Long Division solution to our problem.

## 24/100 Long Division Method

We start solving a problem using the Long Division Method by first taking apart the division’s components and comparing them. As we have 24, and 100 we can see how 24 is Smaller than 100, and to solve this division we require that 24 be Bigger than 100.

This is done by multiplying the dividend by 10 and checking whether it is bigger than the divisor or not. If it is then we calculate the Multiple of the divisor which is closest to the dividend and subtract it from the Dividend. This produces the Remainder which we then use as the dividend later.

Now, we begin solving for our dividend 24, which after getting multiplied by 10 becomes 240.

We take this 240 and divide it by 100, this can be seen done as follows:

240 $\div$ 100 $\approx$ 2

Where:

100 x 2 = 200

This will lead to the generation of a Remainder equal to 240 – 200 = 40, now this means we have to repeat the process by Converting the 40 into 400 and solving for that:

400 $\div$ 100 $=$ 4

Where:

100 x 4 = 400

This, therefore, produces another remainder which is equal to 400 – 400 = 0.

Finally, we have a Quotient generated after combining the three pieces of it as 0.24 = z, with a Remainder equal to 0.

Images/mathematical drawings are created with GeoGebra.


text:
# Tropical Cyclone Inner-Core Dynamics

Guimond, S. (2010). Tropical Cyclone Inner-Core Dynamics: A Latent Heat Retrieval and Its Effects on Intensity and Structure Change; and the Impacts of Effective Diffusion on the Axisymmetrization Process. Retrieved from http://purl.flvc.org/fsu/fd/FSU_migr_etd-3920
Guimond, S. (2010). Tropical Cyclone Inner-Core Dynamics: A Latent Heat Retrieval and Its Effects on Intensity and Structure Change; and the Impacts of Effective Diffusion on the Axisymmetrization Process. Retrieved from http://purl.flvc.org/fsu/fd/FSU_migr_etd-3920


text:
# Conditions for almost sure convergence of processes.

Suppose I have a sequence of (Markov) stochastic processes $\left\{X^n_t:n\in\mathbb N, t\in[0,T]\right\}$ constructed on a common probability space.

None of my $X^n_t$ are continuous in $t$, but there is an almost surely continuous (Itô) process $X_t$ such that for any fixed, monotonic sequence $t_n\to t$ I have $X^n_{t_n} \to X_t$ almost surely.

I'd like to strengthen this result as far as possible, Ideally I'd like to be able to say that with probability one for every $t\in[0,T]$ and every sequence $t_n \to t$ I have $X^n_{t_n}\to X_t$.

Obviously the assumptions here are not enough. For every example in which the strong convergence statement holds I could choose a sequence of iid uniform $S_n\in[0,T]$ and set $X^n_t = 0$ whenever $S_n-t\in\mathbb Q$ which would destroy the result without affecting the assumptions.

My question is, what else do I need to do to get the result?

Is there a known necessary condition or proof schema for aproaching this problem?

-


text:
## Stream: new members

### Topic: fin succ proof coercing to n + 1

#### Yakov Pechersky (Jul 28 2020 at 19:46):

Is there some fin n coercion lemma that is missing? Or should I be using fin.cast_succ? In the following proof. I don't know how to remove % (n + 1) even if I have a hypothesis of i < n.

import tactic.linarith

example {n : ℕ} (i : fin n) : ((i : fin (n + 1)) + 1) = i.succ :=
begin
cases i with i h,
induction i with k hk,
simp [fin.succ],
cases n, linarith, refl,
cases n, linarith,
simp [fin.succ],
/-
case nat.succ, nat.succ
k n : ℕ,
hk : ∀ (h : k < n.succ), ↑⟨k, h⟩ + 1 = ⟨k, h⟩.succ,
h : k.succ < n.succ
⊢ ↑k + 1 + 1 = ⟨k.succ.succ, _⟩
-/
sorry,
end

#### Yakov Pechersky (Jul 28 2020 at 20:15):

Even this is confusing me. I'm unable to use h with hi.

example (i n : ℕ) (h : i < n) : (i : fin (n + 1)).val = i :=
begin
induction i with i hi,
simp,
sorry,
end

#### Kevin Buzzard (Jul 28 2020 at 20:48):

I don't think you need induction to prove this. There's bound to be a lemma in the library saying that if i<j then i%j=i, it will be called mod_lt or something

#### Jalex Stark (Jul 28 2020 at 20:50):

the code you posted doesn't say anything about %

#### Kevin Buzzard (Jul 28 2020 at 20:53):

Addition on fin uses % IIRC

#### Johan Commelin (Jul 28 2020 at 20:59):

I would avoid the cast from nat to fin (n+1). It isn't "nice" (imho)

#### Johan Commelin (Jul 28 2020 at 21:00):

But if you really need to, you can do it. The file zmod.lean will show you how to deal with it.

#### Jalex Stark (Jul 28 2020 at 21:03):

I had to guess that the lemma I wanted started with fin.coe_. I spent about a minute trying other things before making this guess.

example (i n : ℕ) (h : i < n) : (i : fin (n + 1)).val = i :=
begin
apply fin.coe_coe_of_lt, linarith,
end

Last updated: May 13 2021 at 18:26 UTC


text:
# Why would you introduce a constant in a moving average model, when you already have the option of differencing?

In the online forecasting book of Hyndman (https://otexts.com/fpp2/MA.html) firstly the use of differencing is explained. After that he shows the formula for a moving average model:

$$y_t = c + \varepsilon_t + \theta_1 \varepsilon_{t-1} + \theta_2 \varepsilon_{t-2} + \ldots + \theta_q \varepsilon_{t-q}$$

I don't see why to add the constant denoted by 'c' in the upper formula. Is there any difference between introducing 'c' and using first differencing before trying to fit a MA model? Furthermore, introducing 'c' would imply that it actually ís allowed to have a nonstationary time series. It seems like I'm making a mistake in my thinking...

The two are not equivalent.

If you difference an invertible MA and fit another MA, the differenced population model is not invertible (this is overdifferencing).

The first most obvious issue is if you try to fit an MA of the same order you started with you get a different model. Consider an MA(1):

$$y_t = c + \epsilon_t + \theta_1 \epsilon_{t-1}$$

and its first difference:

$$\begin{eqnarray} y_t - y_{t-1} &=& c-c + \epsilon_t + \theta_1 \epsilon_{t-1} - \epsilon_{t-1} - \theta_1 \epsilon_{t-2}\\ &=& \epsilon_t - (1-\theta_1) \epsilon_{t-1} - \theta_1 \epsilon_{t-2} \end{eqnarray}$$

Well it got rid of the $$c$$ but it's no longer an MA(1). So we immediately see the differenced model is not equivalent to the model with a constant.

It looks like an MA(2) with the two parameters related. But it's no longer invertible; it has a root on the unit circle. In this case the algebra to see it is straightforward, but I'm going to show you the observed effect on the inverse characteristic roots for a simulated series (since that's something you could do with real data that might help you notice you have overdifferenced).

First I generated 109 observations from an MA(1) with $$\theta_1= -0.5$$ (in your parameterization) and $$c=13.1$$, and $$\sigma=1$$ by hand (this is two short lines in R).

Then using Rob Hyndman's code here I generated a plot of the inverse roots for an MA(1) fitted to the y, and an MA(1) fitted to the differenced y (since that's what we'd do if we naively assumed we'd only got rid of the constant without changing anything else), and then an MA(2) fitted to the differenced y (which is what we'd do if we did the above algebra and noticed it looked like an MA(2)).

We can see in both plots for the differenced series - whether we fitted an MA(1) or an MA(2) that there's a root on (or extremely close to) the unit circle. This makes it clear that we fundamentally changed the characteristics of the model by differencing an already stationary-and-invertible series.

Having a constant $$c$$ doesn't make the series nonstationary. If you start with a stationary series, you don't want to difference it.

The R code I used (after running the code to define the functions on Rob's page at the link above):

 eps <- rnorm(110)
y <- 13.1 + eps[2:110] -.5*eps[1:109]
par(mfrow=c(1,3))
plot(maroots(Arima(y,c(0,0,1))))
plot(maroots(Arima(diff(y),c(0,0,1))))
plot(maroots(Arima(diff(y),c(0,0,2))))
# don't forget to set the mfrow parameter back


text:
## Friday, December 2, 2016

### Grab bag of problems

Sadly, I  have to miss Math club on Tue. given a family emergency. In the meantime, these are some of the problems I've enjoyed looking at recently that I might use sometime soon:

I've reached that point when I see something like this that I think: huh if I form a  right triangle using B to H as the hypotenuse, the remainder of one side is 3/5 r and the hypotenuse is r to the other side must be 4/5 r so its a 3-4-5 triangle.  There are a 1:3 and 1:2 triangle embedded on the edges of the circles as well.  To actually prove this is true just takes the Pythagorean theorem in my version but I suspect there are several other means to the same end. I'd probably scaffold this a bit.

A lovely factoring and deduction exercise. Not too hard beyond the large numbers.  Actually what might be fun is to adapt this and do it interactively in club.

You only need to find the ratio in one of the eight wedges (I drew in ABU) to find the total answer.
Also you could draw a different wedge by extending the inner triangle IJU but I find the first form a bit easier to reason about. Note: the 45-45-90 triangles and the other similar ones. The answer can be found through a combination of similar triangles and area addition starting from the 45-45-90.

The kids actually did this one. It was my second favorite to discuss. My first solution was a rather tedious exercise in the Pythagorean Theorem. There is a similar triangle version that is much simpler.

Some lovely divisibility rule practice embedded in this puzzle.

Find the smallest possible value of the expression:

$$\sqrt{a^2 + 9} + \sqrt{(b-a)^2 + 4} + \sqrt{(8 - b)^2 + 16}$$

This looks complex but ultimately boils down to the shortest distance between n points is a line! Unfortunately it needs a tiny bit of algebra to recognize the geometric representation and find the line so I'll have to save it for some time in the future.


text:
# How to obtain the steady state response of the sampled periodic signal data?

Below the green plot Vin is 5Hz sine voltage signal from a function generator output sampled at 12kHz sampling rate:

The blue plot Vout is the processed/filtered data by using the following code in Python:

#Transfer function
fc = 1 # roll off freq
wc = 2*numpy.pi*fc
sys = signal.lti([1], [1/wc, 1])  # transfer function

#Output in time (Response of the filter to the input)
tout, v_out, x = signal.lsim(sys, v_in, time)  # output

And here is Vout in a more detailed view:

Basically I define a low pass filter transfer function using: sys = signal.lti([ 1 ], [1/wc, 1]).

Then the Vout is obtained from tout, v_out, x = signal.lsim(sys, v_in, time)

So Vout is the filtered response of Vin.

If you compare the Vin and Vout in above plots, Vout looks like it is processed like in Laplace domain, that is to say Vout looks like it is both the transient and steady state response of Vin.

(This problem seen more obvious for a DC input; the output Vout becomes like a transient response of an RC filter)

Having the sampled data like in green plot Vin, how can we obtain a steady sate response of such filter? Or at least close to steady state.


text:
# Can planar set contain even many vertices of every unit equilateral triangle?

Is there a nonempty planar set that contains $$00$$ or $$22$$ vertices from each unit equilateral triangle?

I know that such a set cannot be measurable. In fact, my motivation is to extend a Falconer-Croft proof that works for measurable sets, see the details here. In more general, to make their proof work for other sets besides equilateral triangles, one can ask the following.

Suppose we are given two sets, $$SS$$ and $$AA$$ in the plane, such that $$SS$$ is finite, with a special point, $$s0s_0$$, while neither $$AA$$ nor its complement is a null-set, i.e., the outer Lebesgue measure of $$AA$$ and $$Ac=R2∖AA^c=\mathbb R^2\setminus A$$ are both non-zero. Can we find two congruent copies of $$SS$$, $$f1(S)f_1(S)$$ and $$f2(S)f_2(S)$$, such that $$f−11(f1(S)∩A)Δf−12(f2(S)∩A)={s0}f_1^{-1}(f_1(S)\cap A)\Delta f_2^{-1}(f_2(S)\cap A)=\{s_0\}$$, i.e., $$s0s_0$$ is the only element of $$SS$$ that goes in to/out of $$AA$$ when we go from $$S1S_1$$ to $$S2S_2$$?

I am probably misunderstanding something. Let me suppose a non empty planar set with the property, and that point A is in the set. Pick a unit equilateral triangle having A as a vertex, and also B and C.

Then exactly one of B and C is in the set. If we pick unit equilateral triangle BCD, then D (short for Different from A) must be in the set with A. So if A is in the set, then every point with distance r (where r^2 is 3) from A is in the set.

The contradiction comes from picking arbitrary point X and stepping to it from A using steps of length r, which I leave to you.

Afterthought For your more general question, I would consider studying the following scheme, which may be in the literature: Given S, consider A-colorings of S. These are labellings of S depending on your allowed coloring scheme. For the general problem above, let red correspond to “out of A”, green to “not out of A”, and you color according to how you transform S to a domain containing A. For the problem above, you color a triplet corresponding to the appearance of vertices of a unit equilateral triangle inside or outside the set A.

Now a challenging problem is to determine what A-colorings are interesting/feasible, when you put restrictions on the set of transforms of S. You want to find two colorings which differ precisely at the point $$s0s_0$$. You may be able to prove existence by cardinality considerations on the set of all allowed A-colorings.

Gerhard “Please Show Me What’s Wrong” Paseman, 2019.08.18.


text:
# Code Component¶

The Code Component can be used to insert short pieces of python code into your experiments. This might be create a variable that you want for another Component, to manipulate images before displaying them, to interact with hardware for which there isn’t yet a pre-packaged component in PsychoPy (e.g. writing code to interact with the serial/parallel ports). See code uses below.

Be aware that the code for each of the components in your Routine are executed in the order they appear on the Routine display (from top to bottom). If you want your Code Component to alter a variable to be used by another component immediately, then it needs to be above that component in the view. You may want the code not to take effect until next frame however, in which case put it at the bottom of the Routine. You can move Components up and down the Routine by right-clicking on their icons.

Within your code you can use other variables and modules from the script. For example, all routines have a stopwatch-style Clock associated with them, which gets reset at the beginning of that repeat of the routine. So if you have a Routine called trial, there will be a Clock called trialClock and so you can get the time (in sec) from the beginning of the trial by using::

currentT = trialClock.getTime()

To see what other variables you might want to use, and also what terms you need to avoid in your chunks of code, compile your script before inserting the code object and take a look at the contents of that script.

Note that this page is concerned with Code Components specifically, and not all cases in which you might use python syntax within the Builder. It is also possible to put code into a non-code input field (such as the duration or text of a Text Component). The syntax there is slightly different (requiring a $to trigger the special handling, or \$ to avoid triggering special handling). The syntax to use within a Code Component is always regular python syntax.

## Parameters¶

The parameters of the Code Component simply specify the code that will get executed at 5 different points within the experiment. You can use as many or as few of these as you need for any Code Component:

Begin Experiment:

Things that need to be done just once, like importing a supporting module, initialising a variable for later use.

Begin Routine:

Certain things might need to be done just once at the start of a Routine e.g. at the beginning of each trial you might decide which side a stimulus will appear

Each Frame:

Things that need to updated constantly, throughout the experiment. Note that these will be executed exactly once per video frame (on the order of every 10ms), to give dynamic displays. Static displays do not need to be updated every frame.

End Routine:

At the end of the Routine (e.g. the trial) you may need to do additional things, like checking if the participant got the right answer

End Experiment:

Use this for things like saving data to disk, presenting a graph(?), or resetting hardware to its original state.

## Example code uses¶

### 1. Set a random location for your target stimulus¶

There are many ways to do this, but you could add the following to the Begin Routine section of a Code Component at the top of your Routine. Then set your stimulus position to be $targetPos and set the correct answer field of a Keyboard to be$corrAns (set both of these to update on every repeat of the Routine).:

if random()>0.5:
targetPos=[-2.0, 0.0]#on the left
corrAns='left'
else:
targetPos=[+2.0, 0.0]#on the right
corrAns='right'

### 4. End a loop early.¶

Code components can also be used to control the end of a loop. See examples in Recipes:builderTerminateLoops.

## What variables are available to use?¶

The most complete way to find this out for your particular script is to compile it and take a look at what’s in there. Below are some options that appear in nearly all scripts. Remember that those variables are Python objects and can have attributes of their own. You can find out about those attributes using:

dir(myObject)

Common PsychoPy variables:

• expInfo: This is a Python Dictionary containing the information from the starting dialog box. e.g. That generally includes the ‘participant’ identifier. You can access that in your experiment using exp[‘participant’]

• t: the current time (in seconds) measured from the start of this Routine

• frameN: the number of /completed/ frames since the start of the Routine (=0 in the first frame)

• win: the Window that the experiment is using

• anything you’ve created in a Code Component is available for the rest of the script. (Sometimes you might need to define it at the beginning of the experiment, so that it will be available throughout.)

• the name of any other stimulus or the parameters from your file also exist as variables.

• most Components have a status attribute, which is useful to determine whether a stimulus has NOT_STARTED, STARTED or FINISHED. For example, to play a tone at the end of a Movie Component (of unknown duration) you could set start of your tone to have the ‘condition’

myMovieName.status==FINISHED

Selected contents of the numpy library and numpy.random are imported by default. The entire numpy library is imported as np, so you can use a several hundred maths functions by prepending things with ‘np.’:

• random() , randint() , normal() , shuffle() options for creating arrays of random numbers.

• sin(), cos(), tan(), and pi: For geometry and trig. By default angles are in radians, if you want the cosine of an angle specified in degrees use cos(angle*180/pi), or use numpy’s conversion functions, rad2deg(angle) and deg2rad(angle).

• linspace(): Create an array of linearly spaced values.

• log(), log10(): The natural and base-10 log functions, respectively. (It is a lowercase-L in log).

• sum(), len(): For the sum and length of a list or array. To find an average, it is better to use average() (due to the potential for integer division issues with sum()/len() ).

• average(), sqrt(), std(): For average (mean), square root, and standard deviation, respectively. Note: Be sure that the numpy standard deviation formula is the one you want!

• np.______: Many math-related features are available through the complete numpy libraries, which are available within psychopy builder scripts as ‘np.’. For example, you could use np.hanning(3) or np.random.poisson(10, 10) in a code component.


text:
# Question 0b840

May 17, 2017

$2.5 \cdot 4.8 = 12 k g m {s}^{-} 1$

#### Explanation:

Given:
Mass is a scalar quantity:

$m = 2.5 \text{kg}$

Velocity is a vector:

$\vec{v} = 4.8 \text{m"/"s"" South}$

Momentum is a vector in the same direction as the velocity vector:

$\vec{p} = m \left(\vec{v}\right)$

Substitute in the given quantities:

vecp = 2.5"kg"(4.84.8"m"/"s"" South")#

$\vec{p} = 12 \text{kg m"/"s"" South}$


text:
# Convexity Hypothesis in Rudin 9.10

If $f$ is a real function defined in a convex open set $E \subset \mathbb{R}^n$ such that the partial derivative of $f$ with respect to, say, $x_1$ is identically $0$, we want to show that $f$ depends on ly on the other variables.

It is easy to do this proof using the convexity hypothesis. We can write down two points $f(x_1', ..., x_n)$ and $f(x_1'', x_2, ... x_n)$, and draw the line between them. This line lies entirely in $E$. The Mean Value Theorem applies on this line, and implies that there is some point in the interior $c$ so that the $x_1$ derivative at $c$ is equal to $$\frac{f(x_1'', x_2, ..., x_n) - f(x_1', x_2, ..., x_n)}{x_1'' - x_1'}$$ But this derivative is $0$, and so it follows $f$ is independent of $x_1$.

Rudin continues, asking the reader to find a weaker condition which suffices, and to find examples showing that some condition is necessary. I think for this last part, we can do something simple enough. We can maybe take a horizontal slice out of the plane, and define a function which is $0$ on the bottom half and left side of the plane, but in the first quadrant varies with $y$. We can probably do this in a way which is continuous and differentiable, I just haven't thought about it quite long enough yet.

Anyway, the real question that has me stuck is what the weaker condition should be. If I had to take a guess, I'd guess star-shapedness, but I seem to be struggling to prove this. Or maybe it's wrong all together.

• I would guess that the sets $E_{ (x_2,...,x_n) } = \{x_1 | (x_1,...,x_n) \in E \}$ should be intervals. – copper.hat May 8 '17 at 3:42
• That seems like a good idea. I'll try that. – Alfred Yerger May 8 '17 at 3:44


text:
# ENGR 112 Terms

## 15 terms

### What is mechanics?

The science which describes and predicts the conditions or motion of bodies under the action of forces.

### Statics

Deals with the bodies at rest. (MARE205)

### Dynamics

Deals with the bodies in motion. (MARE206)

gasses

### Non-compressible Fluids

liquids (hydraulics)

∑F=0

F=ma

### Newton's Third Law

for every action there is an equal and opposite reaction

### Newton's Law of Gravitation

w=mg (g=9.8m/s^2)

### Particle

when all of the forces converge at one point

### Rigid Bodies

When all of the forces do not converge on a common point.

Resultant=0

### Law of Sines

sinA/a = sinB/b =sinC/c

### Law of Cosines

a² = b² + c² - 2bc cos α
b² = a² + c² - 2ac cos β
c² = a² + b² -2ab cos γ

Use when given SSS or SAS